Regular Languages

Productions:	A &rarr xB
	A &rarr x
	A,B &isin N
	x &isin T

• Only one nonterminal can appear in any derived string, and it must appear at the right end.

• Equivalent to a deterministic finite automaton (simple program).

• Parser never has to back up or do search.

• Linear parsing time.

• Used for simplest items (identifiers, numbers, word forms).

• Any finite language is regular.

• Any language that can be recognized using finite memory is regular.

Contents    Page-10    Prev    Next    Page+10    Index