BRL-CAD has a long history working with lexer and parser grammars. For the longest time, we used the popular Flex (Lex) and Bison (Yacc) tools for generating parsers but recently are migrating to a new system. In order to demonstrate this new system, we need the simplest possible tutorial in the old system.
This task involves writing a VERY simple demonstration of a flex+bison parser. The goal is to make a simple tutorial that creates a trivial calculator (supporting only +-*/ and perhaps '()' parentheses).
References:
- examples are abundant around the web, search for them
- http://www.cs.man.ac.uk/~pjj/cs5031/ho/node5.html
- http://dinosaur.compilertools.net/bison/bison_5.html
- http://iamsrijon.wordpress.com/2009/12/23/infix-calculator-in-yacc-amp-flex/
- http://epaperpress.com/lexandyacc/
Provide your lex source, yacc source, and a VERY brief tutorial write-up. Remember the emphasis is on simplicity (and brevity).
Do not plagiarize someone else's work from the web. You can use other people's work (where they permit it) as a starting point, but you should cite their contribution to your work and the tutorial text should be your own words.
File name/URL | File size | Date submitted | |
---|---|---|---|
BisonFlexTutorial.txt | 8.4 KB | December 29 2012 19:52 UTC | |
calc.lex | 358 bytes | December 29 2012 19:52 UTC | |
calc.yacc | 604 bytes | December 29 2012 19:52 UTC | |
BisonFlexTutorial2.txt.txt | 8.3 KB | December 29 2012 21:53 UTC | |
calc2.lex | 339 bytes | December 30 2012 00:37 UTC | |
calc2.yacc | 633 bytes | December 30 2012 00:37 UTC | |
BisonFlexTutorial3.txt | 8.4 KB | December 30 2012 00:38 UTC | |
Bison_Flex_Tutorial.txt | 11.6 KB | December 30 2012 21:01 UTC | |
calculator.lex | 466 bytes | December 30 2012 21:01 UTC | |
calculator.yacc | 747 bytes | December 30 2012 21:01 UTC | |
calculator2.yacc | 734 bytes | December 30 2012 21:02 UTC | |
Bison_Flex_Tutorial.zip | 6.0 KB | January 01 2013 04:58 UTC | |
Bison_Flex_Tutorial2.tar.gz | 6.5 KB | January 02 2013 05:21 UTC |
I would like to work on this task.
This task has been assigned to javamonn. You have 48 hours to complete this task, good luck!
The work on this task is ready to be reviewed.
I made a couple spelling fixes and format changes, the second upload of the tutorial is alot cleaner.
Thanks,
Daniel
Daniel,
That looks pretty good, but before critiquing too much more, the lex/yacc files need style cleanup. The indentations are all over the place and aren't even consistent within one file and definitely not across both files. See our HACKING guide about our indentation rules and brace placement for source code. It's C-centric, but most of the rules still apply.
The deadline of the task has been extended with 1 days and 0 hours.
One of the mentors has sent this task back for more work. Talk to the mentor(s) assigned to this task to satisfy the requirements needed to complete this task, submit your work again and mark the task as complete once you re-submit your work.
The work on this task is ready to be reviewed.
Sorry about the wonky formatting, I did it all on my tablet, didn't even think to check how it looked in a real text editor. calc2.lex and calc2.yacc should look alot better now. I also updated the tutorial to fix the code formatting. Let me know if I should change anything else.
Thanks,
Daniel
Still some formatting changes needed. The lexer and parser have a few issues:
I'm guessing from the one blatant syntax error that you didn't try compiling? Your tutorial should show the calculator being compiled and run...
This is looking to be a fantastic tutorial.
One of the mentors has sent this task back for more work. Talk to the mentor(s) assigned to this task to satisfy the requirements needed to complete this task, submit your work again and mark the task as complete once you re-submit your work.
The work on this task is ready to be reviewed.
To avoid confusion, these are the files that are ready for review: Bison_Flex_Tutorial.txt, calculator.lex, and calculator2.yacc. I missed a small formatting issue on the original upload of calculator.yacc so I fixed it and reuploaded.
The tutorial has been edited to include a section on compiling and running the calculator. I also reworked a large portion of the rules section of the lex file, instead of simply returning operators and parenthesis, they are now returned as tokens to better illustrate that concept.
The point of the [ \t] rule is so the calculator can pick up different ways of formatting input. If a user wants to seperate numbers and operators with spaces, the lexer will match the spaces and perform no action when it finds one. Without this rule those spaces and tabs would get echoed back out since Flex sees it as a lack of comprehensive token definitions.
Let me know if there are any other issues or changes you would like me to fix/change.
Thanks,
Daniel
Melange has detected that the deadline has passed and no more work can be submitted. The submitted work should be reviewed.
Tere are still some white-space issues, e.g. new-line in sentences, missing blanks between words or word and punktuation, trailing blanks and tabs.
You should make more paragraphs. It's hard to read.
What's yywrap() and yyparse() good for? (I don't know anything about flex and bison.)
One of the mentors has sent this task back for more work. Talk to the mentor(s) assigned to this task to satisfy the requirements needed to complete this task, submit your work again and mark the task as complete once you re-submit your work.
The deadline of the task has been extended with 2 days and 0 hours.
... you should put all relevant files into one container file (.zip, .tar, ...). This way we know what to review and there will be no confusion in file revisions (e.g. you refer to calculator.yacc in the tutorial but the real file was calculator2.yacc).
The work on this task is ready to be reviewed.
Sorry about the formatting, I had word wrap on before so it looked different on my end. That's fixed now. I also edited the way many sentences were written and added in more paragraphs.
yyparse tells the parser that Bison generated to begin to receive tokens and start parsing. It sets the calculator utility into motion. yywrap is like setting a flag almost, Lex will check to see if it returns 1 or 0 to determine if it should stop scanning input when it comes across an EOF indicator. I added a couple paragraphs to the tutorial to cover these two functions.
Let me know if anything else should be edited.
Thanks,
Daniel
It'll be just a lil bit longer to finish reviewing this. Apologies on the delay, but wanted to give you an update. :)
Thanks for your cleanup efforts.
Daniel, that's starting to look great. It could be condensed a little more but I think it easily fits the bill. The only piece I don't see in the tutorial is an explanation for the lexer tokens. If I'm writing my own lexer+parser, what tokens can be used? How/Why were those names chosen? There should be some brief explanation since that's the first bit of "code" you present. You may even want to lead into explaining what the goal is (e.g., "We going to create a simpel calculator where you can type '1+1' and it tells you 2.") since I don't see that in the intro.
Other questions I didn't see answered, but you maybe covered are why write the lexer first? Does it matter? Is it possible to write a parser without a lexer or a lexer without a parser? What changes?
That's looking fantastic. We'll be creating a follow-on task to convert your tutorial into our new Perplex+Lemon syntax next. ;)
One of the mentors has sent this task back for more work. Talk to the mentor(s) assigned to this task to satisfy the requirements needed to complete this task, submit your work again and mark the task as complete once you re-submit your work.
The deadline of the task has been extended with 1 days and 0 hours.
I added in a paragraph and a half about tokens and how they are used in this utility, as well as in general. I also added info about what can be a token and how they are named.
I added in a line about the end goal of the calculators function in the intro paragraph, I don't know how I left that out to begin with haha.
I covered why I personally wrote the lexer first, but really you can go in any order. I also added a paragraph to address the issue of Flex without Bison and Bison without Flex.
I rewrote a couple paragraphs to change phrasing and combined a few.
I'm pretty happy with the way the tutorial turned out, the only issue I could possibly see now is it's length. Let me know if you think any parts should be shortened or cut entirely. I tried to do as much of that as I could myself by combining a couple paragraphs and eliminating unnecessay sentences.
Thanks,
Daniel
The work on this task is ready to be reviewed.
Congratulations, this task has been completed successfully.
Let me know when you get the Perplex+Lemon task up, it sounds pretty interesting. Flex and Bison was alot of fun.