Sequences of different kinds are very common.īNFC has a special notation for list categories. ListDef ::= Def ListDef - add one moreĪ function definition has a header and a list of statements in curly bracketsĪ header has a type, a name (an identifier), and a parameter declaration list Rules for modules and function definitionsĬonsDef. Statements are built from other statements and expressions.Įxpressions are built from other expressions and atoms. In many languages, the levels are roughly:įunctional languages skip the statement level.Įach file contains a module, which is a sequence of function definitions.Ī definition has a header and a sequence of statemens. Usually it is good to proceed top-down: start from the largest program Writing a grammar: the main programming language structures (The original plan was to give Lisp a separate concrete syntax later!) Lisp notation: the same, but always in parentheses: Haskell notation: label followed by subtrees, in parentheses if necessary:
Notice: from a grammar, both parsing and linearization are created automatically.Ībstract syntax can be expressed as algebraic datatypes. This is the idea of syntax-directed translation. linearize the resulting tree into the target language.parse with the concrete syntax of source language.GF has tools for visualizing trees and word alignment: This leads to more expressive grammars, definable inĬoncrete syntaxes can be different languages.
Lin plus x y = "the sum of" ++ x ++ "and" ++ y - English One could give a separate abstract syntax ruleĪnd functions computing the concrete syntax as linearization: One abstract syntax tree can have infinitely many Exp ::= Exp Exp => plus : (Exp, Exp) -> Exp LHS (left-hand-side) as value type, RHS as argument types: leaves: atoms (= zero-place constructor functions)Īre defined by constructor type signaturesĮxp ::= Exp "+" Exp => plus.nodes: nonterminals (= syntactic categories).
the tree returned by the parser and manipulated by type checker.the tree initially constructed by the parserĪbstract tree (right): show the semantically significant structure.Parse tree (left): show the concrete syntax (how tokens are grouped together)
Next lecture: how to write a grammar to generate a compiler front end.Ībstract syntax: what are the significant parts of the expression?Įxample: a sum expression has its two operand expressions as its significant partsĬoncrete syntaz: what does the expression look like?Įxample: the same sum expression can look in different ways: This lecture: how syntax rules look like.