grammar : Java Glossary

grammar

Computer languages have very strict and fragile grammars. Grammars can be classified by how easy it is to mechanically analyse, that is parse, them. Analysis is usually broken into two phases, breaking the character stream into tokens calling lexing (or scanning), and analysing the relationship of the tokens, called parsing. The lexing part is quite simple, a finite state automaton that flips states when it sees certain character strings, as it processes the input a character at a time, and collects the input into tokens. The parser is a pattern matcher, that looks for legal patterns in the language. It may have to try a great many possible patterns called production rules in the process of analysing.

Very simple languages can be analysed with LL(1) parsers, Left-to-right scan, Leftmost derivation. This means you can decide what something is without look-ahead or backtracking, just by looking at the next character in the stream. The language to be parsed is described with a hierarchical enumeration of all possible legal programs.
LL(k) recursive-descent parsers are a generalisation of LL(1), looking ahead k tokens. These are sometimes called top-down parsers. Such parsers can’t support left recursion in the grammatical rules. JavaCC generates LL(k) parsers.
LALR(1) Look Ahead Left to Right grammars do support left recursion. However, LALR(1) parsers have a problem with a "dangling else", but this problem can be resolved with a kludge to remove the ambiguity of whether the algorithm should shift a token onto the stack or should reduce tokens on the stack by using a grammar rule at a particular state. YACC generates LALR parsers.
A more general parser still is LR(1), Left-to-right scan, Rightmost derivation. LR parsers are sometimes called bottom-up parsers. LALR parsers are also bottom up. They are more general but slower than top-down parsers.

The advantages of top down parsers include:

The use of more general grammars (although left-recursion is disallowed).
Easier to debug.
The ability to parse to any non-terminal in the grammar.
The ability to pass values (attributes) both up and down the parse tree during parsing.

recommend book⇒Compilers : Principles, Techniques, and Tools

paperback

hardcover

ISBN13:

978-0-201-10194-2

978-0-201-10088-4

publisher:

Addison Wesley

published:

1986-01-01

by:

Alfred V. Aho, Ravi Sethi and Jeffrey D. Ullman

The classic text to learn about grammars and compiler construction is The Dragon Book.

	abe books.co.uk	abe books.ca
	amazon.co.uk	amazon.ca
	abe books.de	chapters.indigo.ca
	amazon.de	abe books.com
	abe books.fr	amazon.com
	amazon.fr	barnes and noble.com
	abe books.it	powells.com
	iberlibro.com	sony e-books
	abe books anz

parser

	You can get the freshest copy of this page from:	or possibly from your local J: drive (Java virtual drive/mindprod.com website mirror)
	http://mindprod.com/jgloss/grammar.html	J:\mindprod\jgloss\grammar.html
	Please email your feedback for publication, errors, omissions, typos, formatting errors, ambiguities, unclear wording, broken/redirected link reports, suggestions to improve this page or comments to Roedy Green :
	Canadian Mind Products
	mindprod.com IP:[65.110.21.43]
view Blog	Your face IP:[38.107.191.100]
Feedback	You are visitor number 10,492.