M2 – 4/4: Context Free Grammars

What are the nonterminal symbols in a grammar?

A name on the left of a rewrite rule

What are the terminal symbols in a grammar?
Example: Non-terminals expr, term, digit-seq

The actual characters that end up in your program, can’t be rewritten further, and terminate the rewriting process: +, -, *, 0-9, (, )

Draw the derivation tree 4+6×2

Why is 6 a term and 2 a factor?

Same logic as #1, just one level down. The rule used for 6*2 was:

term → term mult-op factor

This has three slots again. * fills mult-op, so:

• Everything left of * fills the term slot → 6

• Everything right of * fills the factor slot → 2

What are the nonterminal & terminal symbols in this CFG?

nonterminals: expr, term, factor, add-op, mult-op, digit-seq, digit
terminals:

• + | -

• * | DIV | REM

• 0 | 1 | 2… | 9

When is a string invalid according to the grammar?

• A symbol appears that no rule can produce (e.g. % isn't in any rule)

• The structure doesn't match any rule (e.g. two operators in a row 4++2)

• It's incomplete — you can't finish rewriting all non-terminals (e.g. just +)

• If you get stuck — meaning no rule can produce what you need — the string is invalid.

What is the standard precedence latter and what does low/high precedence mean?

Low precedence = sits at the top of the tree
High precedence = sits deeper in the tree

The standard precedence ladder (you just have to memorize this)

+ and -     → lowest precedence (top of tree)
* and /     → highest precedence