Grammar Definition

A - a
A $\in$ N
a $\in$ V*

Since left-hand-side of each production is a single nonterminal, every derivation is a tree.

Memory Needed for Parsing.

Recursive program = a stack for temporary storage

Notations for defining the syntax of a language :

BNF

Pascal-style transition diagrams.

Ambiguous grammars VS unambiguous grammars

Ambiguous : grammar for which some sentence has more than one parse tree is ambiguous. There’s two way to deal with this. Re-write the grammar and User disambiguating rules to guide the parser.

Augmented transition network;Yacc

• Arbitrary tests : can be added to the arcs.
• Structure-building actions : can be added to the arcs. These actions may save information in registers to be used later by the parser, or to build the representation of the meaning of the sentence. Transformations, can also be handled.
• Phrase names : as well as part-of-speech names, may appear on arcs. This allows a grammar to be called as a subroutine.

What kinds of language constructs are context-free?

Arithmetic expressions, noun pharses.
Any language that requires counting must be at least context free.

Citation:

• Aho, Lam, Sethi, & Ullman, Compilers: Principles, Techniques, and Tools
• UT Austin CS375: Compilers by G.Novak.