Compilers Notes

Compilers.md

Definition of Grammars

A context-free grammar has four components:

1. A set of terminal symbols, sometimes referred to as "tokens." The terminals are the elementary symbols of the language defined by the grammar.
2. A set of nonterminals, sometimes called "syntactic variables." Each non­terminal represents a set of strings of terminals, in a manner we shall describe.
3. A set of productions, where each production consists of a nonterminal, called the head or left side of the production, an arrow, and a sequence of terminals and/or nonterminals, called the body or right side of the produc­ tion. The intuitive intent of a production is to specify one of the written forms of a construct; if the head nonterminal represents a construct, then the body represents a written form of the construct.
4. A designation of one of the nonterminals as the start symbol.

Formally, given a context-free grammar, a parse tree according to the gram­mar is a tree with the following properties:

1. The root is labeled by the start symbol.
2. Each leaf is labeled by a terminal or by €
3. Each interior node is labeled by a nonterminal.
4. 4. If A is the nonterminal labeling some interior node and Xl , X2 , • • • , Xn are the labels of the children of that node from left to right, then there must be a production A -> XIX2···Xn. Here, XI,X2,... ,Xn each stand for a symbol that is either a terminal or a nonterminal. As a special case, if A -> € is a production, then a node labeled A may have a single child labeled €.