06-12-2008, 01:23 PM
|
#19
|
|
Developer
Join Date: Jul 2005
Posts: 104
|
PirataNervo, google "shift-reduce" parser design
It's a very simple and yet very powerful.
But most explanations of it suck =3
So here I'll "try":
Step 1: Load the code
Code:
//A variable
int variable;
//A function
int function()
{
}
Step 2: Strip comments
Code:
int variable;
int function()
{
}
Step 3: Tokenize
(a linked list if you will)
Code:
TEXT(int) -> TEXT(variable) -> OPERATOR(;) -> TEXT(int) -> TEXT(function) -> OPERATOR(() -> OPERATOR()) -> OPERATOR({) -> OPERATOR(})
Step 4: Parse
(where most people fail is right here, but it's simple really)
We have a list of patterns:
(TEXT_ARG = takes in an argument)
(TEXT = EXPECTS a certain text to appear)
(OPERATOR_ARG = takes in an OPERATOR)
(OPERATOR = EXPECTS a certain operator to appear)
Code:
Pattern 1:
--name: VARIABLE_START
--pattern to expect=TEXT_ARG -> TEXT_ARG
--LookAhead CANNOT be one of these:
----OPERATOR(()
Pattern 2:
--name: VARIABLE
--pattern to expect=VARIABLE_START -> OPERATOR(;)
Pattern 3:
--name: FUNCTION_PARAM_START
--pattern to expect=TEXT_ARG -> TEXT_ARG -> OPERATOR(()
Pattern 4:
--name: FUNCTION_PARAM_END
--pattern to expect=FUNCTION_PARAM_START -> OPERATOR())
Pattern 5:
--name: CODE_BLOCK
--pattern to expect=OPERATOR({) -> OPERATOR(})
Pattern 6:
--name: FUNCTION
--pattern to expect=FUNCTION_PARAM_END -> CODE_BLOCK
We have our token list:
Code:
TEXT(int) -> TEXT(variable) -> OPERATOR(;) -> TEXT(int) -> TEXT(function) -> OPERATOR(() -> OPERATOR()) -> OPERATOR({) -> OPERATOR(})
Next we write a function that:
1) Reads a token from our list, and 'pushes' it onto a stack
2) So we read the first token, TEXT(int)
Stack=TEXT(int)
3) We also set a LOOK AHEAD token which points to the next token
LookAhead=TEXT(variable)
4) We then look through our list of patterns to see if we find a match
5) No match found, push the next token onto the stack
Code:
Stack=TEXT(int) -> TEXT(variable)
LookAhead=OPERATOR(;)
6) We look through our list of patterns, and a pattern "does" match:
Code:
Pattern 1:
--name: VARIABLE_START
--pattern to expect=TEXT_ARG -> TEXT_ARG
--LookAhead CANNOT be one of these:
----OPERATOR(()
We then see that the pattern has a 'LookAhead' ban, and the ban does not apply, so yes, the pattern matches!
7) Now what, that the pattern matched?
The stack before was:
Code:
Stack=TEXT(int) -> TEXT(variable)
LookAhead=OPERATOR(;)
We see that the pattern has two tokens:
--pattern to expect=TEXT_ARG -> TEXT_ARG
So we "pop" these two tokens from the stack:
Code:
Stack=(blank)
LookAhead=OPERATOR(;)
And we push the "reduced" form onto the stack
Code:
Stack=VARIABLE_START
LookAhead=OPERATOR(;)
8) Everytime a pattern match is found, we can use it to build a source code tree.
E.g., when a VARIABLE_START pattern is found, we can do:
compiler_addVariableToDat abase(getValueOfFirstArgT extOccurance, getVal..etc)
9) Now we continue our pattern searching by getting the next token, "OPERATOR(;)"
Which means the stack is now:
Code:
Stack=VARIABLE_STACK -> OPERATOR(;)
LookAhead=TEXT(int)
10) We do a pattern search again, and ahoy! A pattern's found:
Code:
Pattern 2:
--name: VARIABLE
--pattern to expect=VARIABLE_START -> OPERATOR(;)
11) So we pop those two off the stack, and push VARIABLE unto the stack
----------------------------------------------------------
Well, hopefully, this is an interesting read to some.
I'm not gonnah kill it to death by manually 'parsing' the rest of the code
But that should give some an idea of how compilers do things.
I mean, think of it with numbers:
Code:
Pattern 1:
--name: NUMBER
--pattern to expect=NUMBER -> OPERATOR(*) -> NUMBER
Pattern 2:
--name: NUMBER
--pattern to expect=NUMBER -> OPERATOR(/) -> NUMBER
Pattern 3:
--name: NUMBER
--pattern to expect=NUMBER -> OPERATOR(+) -> NUMBER
--LookAhead CANNOT be one of these:
----OPERATOR(*)
----OPERATOR(/)
And let's say our input code is:
What happens?
After the first three tokens are pushed onto the stack,
the parser would try to apply pattern #3
BUT, since the LookAhead would be OPERATOR(*):
Code:
Stack=8+2
LookAhead=*
And pattern 3 PROHIBITS the LookAhead from being * or /,
so pattern 3 does not get applied, and the parser continues:
So we eventually get:
Code:
Stack=8+2*3
LookAhead=END
Pattern 1 applies!
Since pattern 1 has 3 tokens, this means 3 tokens are popped off the stack, leaving:
Code:
Stack=8+
LookAhead=END
But, then the reduced form "NUMBER" gets pushed onto the stack:
Code:
Stack=8+NUMBER
LookAhead=END
And finally, Pattern 3 can apply since the LookAhead is no longer a banned operator
And we get:
Code:
Stack=NUMBER
LookAhead=NULL
----------------------
Fin
----------------------
Important notes:
1) Pattern matching is done from end of stack - and not anywhere in between
2) It is common for Patterns to have the same 'end result' "name" (such as seen above)
Last edited by SANiK; 06-12-2008 at 01:44 PM..
|
|
|
