Grammars

Question 1

What is a grammar?

Answer 1

A grammar is a set of formal rules that define what a valid sentence looks like

Question 2

How is a grammar rule defined computationally?

Answer 2

Each rule describes a pattern against which we match the input string, in terms of literals and other patterns

Question 3

How is a grammar defined formally? (4)

Answer 3

G = (N, T, P, N0)
• N = Set of non-terminals
• T = Set of terminals
• P = Set of productions mapping a non-terminal to a sequence of non-terminals and terminals
• N0 = Initial non-terminal (start symbol)

Question 4

What is meant by an ambiguous grammar?

Answer 4

When a valid sentence has more than one parse tree, that is you can product a valid sentence using more than one different sequence of productions