Modile 2.4: Grammar Ambiguity

Vocabulary flashcards covering grammar parsing, parse tree structures, and the definition and resolution of ambiguity based on Module 2 - Topic 4.

Parse Tree

A hierarchical derivation where leaf nodes are terminals and non-leaf nodes are non-terminals.

Terminals

The components of a grammar that occupy the leaf nodes of a parse tree.

Non-terminals

The components of a grammar that occupy the non-leaf nodes of a parse tree.

Parsing

A process which takes a sentence and breaks it into its component parts, deriving a parse tree using a tool called a parser.

Illegal Sentence

A sentence for which the parser cannot generate a parse tree.

Ambiguous Grammar

A grammar that generates a sentential form that has two or more distinct parse trees.

Scanner

A tool called during the parsing process to get tokens from the input stream.

Symbol Table

A structure where information about identifiers is added during the parsing process.

Error Recovery

The stage in parsing where the system reports an error, when found, and recovers from it.

Grammar Rewriting

The process of taking an ambiguous grammar and modifying it to be unambiguous while still generating the desired language.