Java Glossary : grammar
Last updated 2004-06-28 by Roedy
Green ©1996-2004 Canadian Mind Products
Java definitions: 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
You are here : home : Java
Glossary : G words : grammar.
- 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.
 | Compilers : Principles, Techniques, and Tools |
| 0-201-10088-6 |
| Alfred V. Aho, Ravi Sethi and Jeffrey D. Ullman |
| The classic text to learn about grammars and compiler construction is The Dragon Book. |
|
|
