Programming Language Theory: Difference between revisions
| Line 33: | Line 33: | ||
This abstract grammar can be augmented with associativity rules and grouping syntax (parentheses) to provide a concrete grammar. If verbosity is no issue, no associativity rules need be specified for the following grammar: | This abstract grammar can be augmented with associativity rules and grouping syntax (parentheses) to provide a concrete grammar. If verbosity is no issue, no associativity rules need be specified for the following grammar: | ||
<pre>λ-term ::= λ-app | λ-abst | var | <pre>λ-term ::= λ-app | λ-abst | var | ||
λ-app ::= '('λ-term λ-term')' | λ-app ::= '(' λ-term λ-term ')' | ||
λ-abst ::= '(''λ'var'.' λ-term')'</pre> | λ-abst ::= '(' 'λ'var'.' λ-term ')'</pre> | ||
====Encodings==== | ====Encodings==== | ||
The integers (or any countably infinite set) can be represented via the [http://en.wikipedia.org/wiki/Church_encoding Church encoding] (or [http://en.wikipedia.org/wiki/Mogensen-Scott_encoding Mogensen-Scott], or others): | The integers (or any countably infinite set) can be represented via the [http://en.wikipedia.org/wiki/Church_encoding Church encoding] (or [http://en.wikipedia.org/wiki/Mogensen-Scott_encoding Mogensen-Scott], or others): | ||