Create a flex+bison tutorialBRL-CAD
Status: ClosedTime to complete: 48 hrs Mentors: SeanTags: demo application, tutorial, example, bison, flex, yacc, lex

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.

Uploaded Work
File name/URLFile sizeDate submitted
BisonFlexTutorial.txt8.4 KBDecember 29 2012 19:52 UTC
calc.lex358 bytesDecember 29 2012 19:52 UTC
calc.yacc604 bytesDecember 29 2012 19:52 UTC
BisonFlexTutorial2.txt.txt8.3 KBDecember 29 2012 21:53 UTC
calc2.lex339 bytesDecember 30 2012 00:37 UTC
calc2.yacc633 bytesDecember 30 2012 00:37 UTC
BisonFlexTutorial3.txt8.4 KBDecember 30 2012 00:38 UTC
Bison_Flex_Tutorial.txt11.6 KBDecember 30 2012 21:01 UTC
calculator.lex466 bytesDecember 30 2012 21:01 UTC
calculator.yacc747 bytesDecember 30 2012 21:01 UTC
calculator2.yacc734 bytesDecember 30 2012 21:02 UTC
Bison_Flex_Tutorial.zip6.0 KBJanuary 01 2013 04:58 UTC
Bison_Flex_Tutorial2.tar.gz6.5 KBJanuary 02 2013 05:21 UTC
Comments
javamonnon December 28 2012 00:21 UTCTask Claimed

I would like to work on this task.

Harmanpreet Singh on December 28 2012 06:48 UTCTask Assigned

This task has been assigned to javamonn. You have 48 hours to complete this task, good luck!

javamonnon December 29 2012 19:52 UTCReady for review

The work on this task is ready to be reviewed.

javamonnon December 29 2012 21:54 UTCUse the second one...

I made a couple spelling fixes and format changes, the second upload of the tutorial is alot cleaner. 


Thanks, 


Daniel

Sean on December 29 2012 22:44 UTCstyle cleanup

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.


 

Sean on December 29 2012 22:45 UTCDeadline extended

The deadline of the task has been extended with 1 days and 0 hours.

Sean on December 29 2012 22:45 UTCTask Needs More Work

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.

javamonnon December 30 2012 00:38 UTCReady for review

The work on this task is ready to be reviewed.

javamonnon December 30 2012 00:40 UTCSorry about that.

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

Sean on December 30 2012 04:25 UTCchanges

Still some formatting changes needed.  The lexer and parser have a few issues:



  • The %{ definition section shouldn't be indented (it's included literally) and has a blatant error ...

  • the return INTEGER; line is indented wrong

  • the yywrap() formatting doesn't match our style, open paren should be on new line and indent should be just four spaces.  the two parser functions, yyerror() and main() have similar formatting problems.

  • what's the point of the [ \t] rule?


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.


 

Sean on December 30 2012 04:25 UTCTask Needs More Work

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.

javamonnon December 30 2012 21:03 UTCReady for review

The work on this task is ready to be reviewed.

javamonnon December 30 2012 21:09 UTCSome notes:

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 on December 31 2012 06:50 UTCNo more Work can be submitted

Melange has detected that the deadline has passed and no more work can be submitted. The submitted work should be reviewed.

Daniel Rossberg on December 31 2012 16:11 UTCIt still needs some polish

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.)

Daniel Rossberg on December 31 2012 16:11 UTCTask Needs More Work

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.

Daniel Rossberg on December 31 2012 16:11 UTCDeadline extended

The deadline of the task has been extended with 2 days and 0 hours.

Daniel Rossberg on December 31 2012 16:21 UTCAnd ...

... 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).

javamonnon January 1 2013 04:58 UTCReady for review

The work on this task is ready to be reviewed.

javamonnon January 1 2013 05:09 UTCPolished it

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

Sean on January 1 2013 19:15 UTClil longer

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.

Sean on January 1 2013 22:23 UTCalmost there

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. ;)

Sean on January 1 2013 22:23 UTCTask Needs More Work

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.

Sean on January 1 2013 22:23 UTCDeadline extended

The deadline of the task has been extended with 1 days and 0 hours.

javamonnon January 2 2013 05:29 UTCList of changes:

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

javamonnon January 2 2013 05:29 UTCReady for review

The work on this task is ready to be reviewed.

Sean on January 2 2013 06:42 UTCTask Closed

Congratulations, this task has been completed successfully.

javamonnon January 2 2013 08:01 UTCPerplex+Lemon

Let me know when you get the Perplex+Lemon task up, it sounds pretty interesting. Flex and Bison was alot of fun.