Yacc and stuff.
September 19, 2003 01:26 PM
Can some one explain to me about yacc/lex/bison and whatever. I was thinking about this and it seems a bit odd. Though I just don''t know enough about it yet, to say is all. So yacc creates a parse ( in C ) but does it then have a kind of "parser language" for creating parsers. And I''m not sure how you get anything our of the parser created. I mean, like I don''t know assembly, or something, do you have to provide class and method names too, then right? Or and interface/structure of some kind. Am I right in thinking this?
" ''No one has control -- control is just a fantasy. And being human is difficult.'' "
"Education is when you read the fine print; experience is what you get when you don't." -Pete Seegerwww.lucid-edge.net
12,313
September 19, 2003 02:34 PM
Yes... when using Yacc to create a parser, it has it's own language that you use to design the language's grammar and rules for your parser.
I find it rather cumbersome to use Yacc to directly generate C code, so I typically write rules with no reduce code and turn on verbose mode. I grab the .v intermediate output file and manually write an SLR parser by hand from that (more efficient I've found).
I've done two main things with SLR parsers: Creating an optimized function that represents the input "compiling", or directly doing what the input would have done anyway "interpreting".
Say with a math parser, you could have the input: "4+x*3"
The language for this parser could be (excuse the fact that this is not geared for any particular grammar precedence form):
A -> A * B
A -> B
B -> B + C
B -> C
C -> integer
C -> variable
A compiler-type parser would turn this into a set of operations:
Load x, multiply by 3, add 4. From that point forward, you wouldn't need to parse the "4+x*3" string every time you wanted to use the function.
An interpreter would get to the x token and load the current value of x (say it's 5) onto the stack, then during the x*3 reduce, it would directly multiply 5 and 3, getting 15 and pushing the result back where x*3 used to be. Then another reduce would happen (4+15) and you would be left with 19 on the stack. This would be an accept case for the parser and you would have the answer simply by popping it off.
[edited by - Nypyren on September 19, 2003 3:39:58 PM]
I find it rather cumbersome to use Yacc to directly generate C code, so I typically write rules with no reduce code and turn on verbose mode. I grab the .v intermediate output file and manually write an SLR parser by hand from that (more efficient I've found).
I've done two main things with SLR parsers: Creating an optimized function that represents the input "compiling", or directly doing what the input would have done anyway "interpreting".
Say with a math parser, you could have the input: "4+x*3"
The language for this parser could be (excuse the fact that this is not geared for any particular grammar precedence form):
A -> A * B
A -> B
B -> B + C
B -> C
C -> integer
C -> variable
A compiler-type parser would turn this into a set of operations:
Load x, multiply by 3, add 4. From that point forward, you wouldn't need to parse the "4+x*3" string every time you wanted to use the function.
An interpreter would get to the x token and load the current value of x (say it's 5) onto the stack, then during the x*3 reduce, it would directly multiply 5 and 3, getting 15 and pushing the result back where x*3 used to be. Then another reduce would happen (4+15) and you would be left with 19 on the stack. This would be an accept case for the parser and you would have the answer simply by popping it off.
[edited by - Nypyren on September 19, 2003 3:39:58 PM]
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
