grammar : Java Glossary

by Roedy Green ©1996-2008 Canadian Mind Products
Go to : punctuation 0-9 A B C D E F G H I J K L M N O P Q R S T U V W X Y Z (all)

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

ISBN10:

0-201-10194-7

0-201-10088-6

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.

	amazon.ca	amazon.com
	chapters.indigo.ca	powells.com
	amazon.fr	barnesandnoble.com
	amazon.de	amazon.co.uk

parser

	Please email your feedback for publication, errors, omissions, broken/redirected link reports and suggestions to improve this page to Roedy Green :
	Canadian Mind Products
	mindprod.com IP:[65.110.21.43]
	Your face IP:[38.103.63.18]
	You are visitor number 8,257.
	You can get a fresh copy of this page from:	or possibly from your local J: drive (Java virtual drive/Mindprod website mirror)
	http://mindprod.com/jgloss/grammar.html	J:\mindprod\jgloss\grammar.html