grammar : Java Glossary

* 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) (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 parse, single token look-ahead) 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 (Yet Another Compiler Compiler) generates LALR (Look Ahead Left-to-Right parse) 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, second edition

Alfred V. Aho, Monica S. Lam, Ravi Sethi, Jeffrey D. Ullman

978-81-3172101-8

paperback

publisher

Prentice Hall

978-0-321-48681-3

hardcover

published

2006-09-10

978-0-13-263452-6

eBook

B004P5NQYI

kindle

Known as the dragon book.

Online bookstores carrying Compilers: Principles, Techniques and Tools, second edition
	abe books anz	abe books.ca
	abe books.de	amazon.ca
	amazon.de	Chapters Indigo
	amazon.es	Chapters Indigo eBooks
	iberlibro.com	abe books.com
	abe books.fr	amazon.com
	amazon.fr	Barnes & Noble
	abe books.it	Nook at Barnes & Noble
	amazon.it	Kobo
	junglee.com	Google play
	abe books.co.uk	O’Reilly Safari
	amazon.co.uk	Powells
	other stores

Greyed out stores probably do not have the item in stock. Try looking for it with a bookfinder.

JLS (Java Language Specification): Java 1.8 Grammar/syntax

grammar checker
parser

standard footer
	This page is posted on the web at:	http://mindprod.com/jgloss/grammar.html
	Optional Replicator mirror of mindprod.com on local hard disk J:	J:\mindprod\jgloss\grammar.html
	Please read the feedback from other visitors, or send your own feedback about the site. Contact Roedy. Please feel free to link to this page without explicit permission.
	Canadian Mind Products IP:[65.110.21.43] Your face IP:[216.73.216.139]
Feedback	You are visitor number