Context Free Grammar And Parsing

Front 1

Context Free Grammar

Back 1

A context free grammar consists of non-terminals and terminals

Front 2

Non-terminal

Back 2

defined by a string of terminals and non-terminals

Front 3

Parsing

Back 3

Parsing is the process of determining how a sentence was generated by the grammar.

The result is a Parse Tree

Front 4

Type 3

Back 4

Regular

The left-hand side of a production rule is a single non-terminal
The right-hand side of a production rule is either
a single terminal
a single non-terminal followed by a terminal or a terminal followed by a single non-terminal (but not both in the same grammar)
Type 3 grammars can be expressed as regular expressions.
Type 3 languages can be recognized by a deterministic finite-state automata.

Front 5

Type 2

Back 5

Context Free

The left-hand side of a production rule is a single non-terminal
The right-hand side of a production rule is a sequence of terminals and non-terminals
Type 2 languages can be recognized by a non-deterministic push-down automata (NP hard)
A sub-set of the type 2 languages can be recognized by a deterministic push-down automata (e.g. a computer program that is either recursive or uses a stack).

Front 6

Type 1

Back 6

Context Sensitive

The left-hand side of a production rule consists of a sequence of terminals and non-terminals that contains at least one non-terminal.
The right hand side is the same sequence with the designated non-terminal replaced by a non-empty sequence of terminals and non-terminals.
e.g. The production rule established a context in which the designated non-terminal can be expanded, and the context is preserved.
Recognizing a type 1 language is NP hard. However, since programming languages are context sensitive, compilers are possible, but the context sensitivity is not part of the language’s formal definition.

Front 7

Type 0

Back 7

Phrase Structured

There is no restriction on either the left-hand side or the right-hand side of a production rule.
Type 0 languages are equivalent to computer programs.
A general-purpose recognizer is not possible.

Front 8

Recursive Decent Parsing

Back 8

Given a context-free grammar one can construct a parser as follows:
Define a method for each non-terminal
This method tries to match each of its choices to the input by looking at the next input token.
If there is a match, the method captures the input token and returns true.
If no match, the method leaves the input stream alone and returns false.

Front 9

Lexer

Back 9

The Lexer parses the input into tokens.
It recognizes that sub-set of the grammar that is regular (e.g. type-3).
The lexer generator lex (flex) which is part of Unix (GNU) is regular-expression based.
A Lexer can also be generated using recursive-decent parsing.

Front 10

Parse Tree

Back 10

records how a sentence is derived from the grammar.

Front 11

Abstract Syntax Tree

Back 11

tree that shows the structure of the sentence.
The internal nodes are terminals or artificial nodes
The leaves are terminals.