9.  Context-Free Grammars, Parse Tree and Parser

This chapter focus on the following topics:

--

Generating and recognizing recursive descriptions of patterns with context-free grammars,

--

Parse tree and

--

Parser

A context-free grammar is a set of recursive rewriting rules (or productions) used to generate patterns of strings. Context-free grammars are often used to define the syntax of programming languages.

A parse tree displays the structure used by a grammar to generate an input string. Parse trees are typically used within a compiler to give structure to an input program in terms of the syntactic rules used to define valid programs.

A parser is an algorithm that determines if a given input string is in a correct sentence in a given language (and, as a side-effect, usually produces a parse tree for the input). There is a procedure for generating a parser of a given context-free grammar.

Last modified 22/May/97