What is the lookahead symbol?
LL(1) grammars help you decide immediately which grammar rule you will use. This one lookahead token means that you only have to read the next one character from the current character you are reading.
LL(1) grammars help you to decrease complexity to O(n)
and have no backtracking on parsing the input.
Let %
to be the character you are reading and the input string to be ( a + a )
A LL(1) grammar :
S -> F (Rule1)
S -> ( S + F ) (Rule2)
F -> a (Rule3)
Parsing Table is :
( ) a + $
S 2 - 1 - -
F - - 3 - -
Then you have:
%( a + a )
( read the start of the string and lookahead is (, so decide to apply Rule2 according to the parsing table)
The abstract syntax tree is now :
S
/ / | \ \
( S + F )
Then you consume (
. And you continue the same way.
Step 2:
S
/ / | \ \
( S + F )
|
F
|
a
Step 3:
S
/ / | \ \
( S + F )
| |
F a
|
a
You can see Wikipedia example that uses a stack, instead of an abstract syntax tree in the exactly same way.
Ellipticat
Updated on June 04, 2022Comments
-
Ellipticat almost 2 years
In the grammars (for example LL(1)), 1 denotes the lookahed symbol. In practice i don't understand what is this symbol. To understand, i need a simple and practical example.
-
arkascha about 9 yearsSuch a lookahead is a symbol that is interpreted "command like" by some processors. It allows to peek ahead, so to read and evaluate a portion of the input stream without actually forwarding the location of the stream. As an effect the next read operation will read the same sequence. The benefit: you can see in advance what you have to expect from the input to come. Sorry, no example at hand currently...
-
Dioxin about 9 yearsSeems like a question for Programmer's StackExchange
-
-
Martin Törnwall about 9 yearsNitpick: the unit of lookahead is tokens, not characters. A token may be comprised of more than one character.