SD05 - Grammars 1

Question 1

What is a language?

Answer 1

A sequence of symbols

Question 2

What is a grammar?

Answer 2

A formal description of a language - a set of rules which define what a valid sentence looks like

Question 3

What is a parser?

Answer 3

A machine which takes a sentence in a language and determines whether or not it adheres to the grammar

Question 4

What is the syntax of a language?

Answer 4

How sentences are formed, not what they mean

Question 5

Why are FSAs not desirable for parsing languages?

Answer 5

They look at input strings one character at a time which is not a ‘natural’ way to think about languages. We tend to think in terms of words

Question 6

What are the two elements of grammars?

Answer 6

Non-terminals (or productions): patterns to match

Terminals (or literals): symbols that actually appear in the input string

Question 7

Is it possible to have a language which contains infinitely many sentences?

Answer 7

Yes
The following grammar can be of infinite length if we keep substituting A for 0A1
A → 0 A 1
A → 0 B 0
B → *

Question 8

What is the 4-tuple of a grammar?

Answer 8

G = (N, T, P, N0
)
Where:
- N is a set of non-terminals
- T is a set of terminals
- P is a set of productions mapping non-terminals to a sequence of non-terminals and terminals
- N0 is the initial non-terminal

Question 9

What is a derivation?

Answer 9

A particular sequence of production applications that yields a string in the language (All symbols are terminals)

Question 10

What is a context-free grammar?

Answer 10

A grammar where any production can be used regardless of where it is in the string

Question 11

In a grammar, what does the ‘|’ symbol mean?

Answer 11

It separates two different expansions for the same non-terminal e.g.:
A -> 0A1 | 1

Question 12

In a grammar, what does the ‘ε’ symbol mean?

Answer 12

It is the empty production, producing no output.

0ε1 = 01