Grammar

Deriving Grammars

Using a provided production/grammar, step through it and replace terminals with the required input strings.

A finite set of rules that describes a language. There can be multiple grammars for the same language.

• Two grammars are weakly equivalent if they accept the same language
• Two grammars are strongly equivalent if they are weakly equivalent and agree on all parse trees

Example

• S → ‘u’|‘w’
• S → A|B
  • A=’u’
  • B=’w’
• These two grammars are weakly equivalent since the AST’s are different

Left vs Right Associative

Left associative grammars group operators of the same precedence to the left whereas right associative grammars group to the right

Things that are have not associativity often need parenthesis to determine precedence.

When designing grammars, choosing associativity and therefore recursion is important.

• Choose right recursive grammars unless you have left associativity.

Regular grammars are a subset of context-free grammars, where regular grammars inherit the LHS restriction of context-free grammars but also have additional RHS restrictions:

• RHS = $ϵ$
• RHS = A single terminal
• RHS = left or right linear
  • This is a single non-terminal followed by a single terminal
  • Or a single terminal followed by a single non-terminal Concepts
• Predict Sets
• Ambiguity