Book "Compiler Construction using Flex and Bison" - problems, discussions, steps, ...

ntubski · 08-31-2016, 11:10 AM

Quote:

Originally Posted by sundialsvcs

Every parser-generator which produces a compilable source-file must provide some means for you to include headers at the top of the generated code, if it does not provide them already. Statements needed to #include the header-files needed by the compiler must be provided-for by appropriate means. These sections will generally be included in the output source-file verbatim.

This is useful general advice, but please note that headers are for declarations, while had the problem mentioned here was a lack of definition.

https://en.wikipedia.org/wiki/Declar...vs._definition

dedec0 · 08-31-2016, 01:40 PM

Thank you for these clarifications, ntubski.

Now I have retried these steps:

Code:

bison -vd ch4.y
flex ch4.lex
gcc -c lex.yy.c
gcc -c ch4.tab.c
gcc lex.yy.o ch4.tab.o -lfl
# Or everything in just one line to read the warnings easier:
# bison -vd ch4.y; flex ch4.lex; gcc -c lex.yy.c; echo ==1; gcc -c ch4.tab.c; echo ==2; gcc lex.yy.o ch4.tab.o -lfl

The compilation of ch4.tab.c had a few problems. I will say what I did for which I "fixed" (not all are good fixes, just to make it work), and then what remains.

1.

Code:

ch4.y:48:1: warning: "YYDEBUG" redefined
ch4.tab.c:76:1: warning: this is the location of the previous definition

Redefined?! There are only two ocurrences of 'define YYDEBUG'. One is in our ch4.y file, the other is a conditional define to 0 in the .c file outputed by Bison. Fixed by commenting the ch4.y:48, which seems wrong or bad: is debugging still active?

2.

Code:

ch4.y: In function ‘install’:
ch4.y:58: error: ‘errors’ undeclared (first use in this function)
ch4.y: In function ‘main’:
ch4.y:128: error: ‘errors’ undeclared (first use in this function)

Fixed by creating a global variable 'Errors' (initialized to 0) and changed those two lines to use it instead of 'errors'. The second use of it was just to initialize it, so I removed that line. Is everything correct? Or 'errors' is somehow provided by flex/bison or the library we use (I searched in Bison doc)?

File ch4.y with all these two changes is below. One problem remains, I do not know what to do:

3.

Code:

ch4.y:130: error: ‘yydebug’ undeclared (first use in this function)

yydebug is mentioned in Bison's documentation (https://www.gnu.org/software/bison/manual/bison.html) but reading there did not ring anything for me. I decided to comment the line that uses it.

4.

Code:

ch4.tab.c:1496: warning: implicit declaration of function ‘yyerror’

I declared the function yyerror we have before the function install, it removed the warning.

There is the -t option for bison to activate debugging, but I think it should also work in the code, which I could not do.

Now I have an a.out that seems to work (I have not played with it yet). But I think the fixes I did are not the best that could be...

There is a warning still there:

Code:

$ gcc -c ch4.tab.c
ch4.tab.c: In function ‘yyparse’:
ch4.tab.c:1349: warning: implicit declaration of function ‘yylex’

This function is not mentioned in our .y file. It is probably in the Flex library -lfl. Should I disconsider this warning? It seems to be something repetitive, probably related with that Flex library. Isn't something missing in the source code or compilation commands?

--------------------------------------------
ch4.y (changes in red):

Code:

%start program

 /* SEMANTIC RECORD */
 /* char *id: For returning identifiers */
 /*
Place to easily pasting/cutting the union declaration
 */

%union {
char *id;
}

/* Simple identifier */
 /*
Place to exchange the IDENTIFIER token declarations
 */
%token IDENTIFIER
%type <id> IDENTIFIER

%token LET IN
/* "integer" keyword */
/* both INT e INTEGER exist? Removed INT, occurrences changed.
%token INT
*/
%token INTEGER

/* Same question for NUMBER: should it exist?
   Replaced all of its occurrences with INTEGER
   -> wrong, written numbers X 'integer' keyword. Changes undone
*/
%token NUMBER

 /* FI was missing */
%token SKIP IF THEN ELSE FI END WHILE DO READ WRITE
     /* ASSGNOP was missing */
%token ASSGNOP 
%left '-' '+'
%left '*' '/'
%left '<' '>' '=' '' /* these where missing on the book, added */
%right '^ '

%{

#include <stdlib.h> /* For malloc in symbol table */
#include <string.h> /* For strcmp in symbol table */
#include <stdio.h> /* For error messages */
#include "st.h" /* The Symbol Table Module */

/* Redeclaration? Should not be. #define YYDEBUG 1 / * for debugging / para depuração */

/*  Global variable 'Errors' to substitute the previously
  undeclared variable 'errors' */
  int Errors = 0;

int yyerror (char *s);     // function header, removes a warning 
int install( char* sym_name)
{
    symrec *s;
    s = getsym(sym_name);
    if (s == 0)
	s = putsym (sym_name);
    else
    {
	Errors++;
	printf("%s is already defined\n", sym_name);
	return 0;
    }
    return 1;
}

int context_check(char* sym_name)
{
    if ( getsym( sym_name ) == 0 )
    {
	printf("%s is an undeclared identifier\n", sym_name);
	return 0;
    }
    return 1;
}


%}

%%

 /* Grammar rules and actions */

program : LET declarations IN commands END ;

declarations : /* empty */
    | INTEGER id_seq IDENTIFIER '.' { install( $3 ); }
;

id_seq : /* empty */
    | id_seq IDENTIFIER ','	    { install( $2 ); }
;
commands : /* empty */
    | commands command ';'
;
command : SKIP
    | READ IDENTIFIER		    { context_check( $2 ); }
    | WRITE exp
    | IDENTIFIER ASSGNOP exp	    { context_check( $1 ); }
    | IF exp THEN commands ELSE commands FI
    | WHILE exp DO commands END
;
 /* expressions */
exp : NUMBER
				    /* in book it is $2, wrong */
   | IDENTIFIER			    { context_check( $1 ); }
   | exp '<' exp
   | exp '=' exp
   | exp '>' exp
   | exp '+' exp
   | exp '-' exp
   | exp '' exp
   | exp '/' exp
   | exp '^ ' exp
   | '(' exp ')'
;

%%

 /* C subroutines */

/* não tem saída, a árvore de reconhec. fica implícita */
/* no output, implicit parse tree */
int main( int argc, char *argv[] )
{
    extern FILE *yyin;
    ++argv; --argc;
    yyin = fopen( argv[0], "r" );
    // yydebug = 1;           // line commented -> bad fix

    // errors = 0;            // initialization unneeded => line removed 
    yyparse ();
    return 0;
}
int yyerror (char *s) /* called by yyparse() in error situations */
{
    printf ("%s\n", s);
    return 0;
}

ntubski · 08-31-2016, 02:55 PM

Quote:

Originally Posted by dedec0

1.

Code:

ch4.y:48:1: warning: "YYDEBUG" redefined
ch4.tab.c:76:1: warning: this is the location of the previous definition

Redefined?! There are only two ocurrences of 'define YYDEBUG'. One is in our ch4.y file, the other is a conditional define to 0 in the .c file outputed by Bison.

I believe the one in the .y file would also end up in the .c file. Somehow you need to arrange that it should go before the conditional generated by bison (so that the condition prevents it from taking effect). Note the all warnings/errors listed as occurring in .y files are really from .c files, but bison puts #line directives in the .c file to tell the compiler which part of the .y file is "responsible" for that code. Then gcc lists .y as the origin of the error so you can fix it in the real source rather than the generated one (which would be overwritten anyway).

Quote:

2.

Code:

ch4.y: In function ‘install’:
ch4.y:58: error: ‘errors’ undeclared (first use in this function)
ch4.y: In function ‘main’:
ch4.y:128: error: ‘errors’ undeclared (first use in this function)

Fixed by creating a global variable 'Errors' (initialized to 0) and changed those two lines to use it instead of 'errors'. The second use of it was just to initialize it, so I removed that line. Is everything correct? Or 'errors' is somehow provided by flex/bison or the library we use (I searched in Bison doc)?

I guess it's just something particular to the C code you had in your bison file, so defining it there makes sense.

Quote:

3.

Code:

ch4.y:130: error: ‘yydebug’ undeclared (first use in this function)

yydebug is mentioned in Bison's documentation (https://www.gnu.org/software/bison/manual/bison.html) but reading there did not ring anything for me. I decided to comment the line that uses it.

4.

Code:

ch4.tab.c:1496: warning: implicit declaration of function ‘yyerror’

I declared the function yyerror we have before the function install, it removed the warning.

Looking at https://www.gnu.org/software/bison/m...n.html#Tracing it seems that those are symbols that bison defines. I guess it should provide declarations as well somehow, but I'm not exactly sure how it's supposed to work.

Quote:

Code:

$ gcc -c ch4.tab.c
ch4.tab.c: In function ‘yyparse’:
ch4.tab.c:1349: warning: implicit declaration of function ‘yylex’

This function is not mentioned in our .y file. It is probably in the Flex library -lfl. Should I disconsider this warning? It seems to be something repetitive, probably related with that Flex library. Isn't something missing in the source code or compilation commands?

I think that's the function produced by flex from your .lex file. Does flex produce a header with declarations? If not I guess you should add a declaration yourself.

astrogeek · 09-01-2016, 03:37 AM

First a personal comment - As this PDF, this alleged Flex/Bison "book" originated from Micro$oft I am inclined to think it is an example of them poisoning the FREE software well by providing examples that are so obscure, incomplete and badly written that they will discourage all who attempt to use them from ever trying to use FREE software again in the future!

Sheeeesh!!

That having been said, I have been able to get the Chapter 4 code to compile and run, with great effort I will add... but what it gets you I do not know...

But first...

Quote:

Originally Posted by dedec0

Two parts:

1. A terminal symbol is one that does [not] change anymore... Nonterminal symbols are variables in the grammar.

As ntubski has pointed out, thinking of a terminal as something that does not change (any more?), and nonterminals as things that do change, totally confuses their use and meaning! That description only has meaning, limited at that, if you keep clearly in mind that the grammar rules are production rules which are applied repeatedly, beginning with the start symbol and ending only when there are no nonterminals on the right hand side of that which is produced. (Think: generative grammars).

I emphasize "production rules" and the direction of the process because that is the direction the parse tree grows, and the parse tree is the ultimate product of the process whether directly visible or not. It is all too easy, and common, to think of the tokens (terminals) as the starting point and the start symbol as the end point because in the code that looks like the direction of "flow" - it is not!

"Variables" reinforces that confusion. I think this terminology is responsible for a great deal of confusion among those trying to learn parsing. Some authors call nonterminals "variables", but that is very far from reality, especially if you think of them as similar to "variables" in a programming language. You are writing a compiler, naturally you want to "see" the grammar as just more code - it is not!

Terminals are symbols that stand-in for some real "word" which can appear in a syntactically correct sentence. Nonterminals are symbols which stand-in for intermediate states* and can never appear in a syntactically correct sentence. Those states, in general, are much more complex than the term "variable" indicates. The start symbol, itself a nonterminal, is just a stand-in for all possible correct sentences which can be produced by the grammar.

*Intermediate states between the start symbol and the terminal state reached by repeated application of the production, or rewriting rules.

My point (much too wordy and not at all as clear as it is in my own brain!) is that you need to really grasp these terms, what exactly grammar is and what the process and product of parsing are. Work to distinguish the grammar and the parsing process from the code - the code your compiler will produce and the code in which the parser is written. It is a separate "thing" altogether.

Quote:

Originally Posted by dedec0

In this book, the convention to use uppercase/lowercase for nonterminal/terminal symbols is different from what we always used in school.

Just to be clear, when I made reference in another post to IDENTIFIER being a terminal and being all upper case, I was saying that it is a terminal because of how it is used in the grammer - being all upper case only indicates that this was the use intended by the author as well.

An upper/lower convention is very helpful when reading the grammer and code, but it is the useage which determines whether a symbol is a terminal or nonterminal.

Quote:

Originally Posted by dedec0

2. I am waiting for an answer and comments in my post about chapter 4

I am way far past my time limit for the day (week!)

so I'll provide more detail in a separate post on this one. Here are a few quick comments to give you something to work on until then...

The code as written in the "book" is not capable of being compiled. That is not due to typos or simple errors - it is just incomplete. I really don't think it was intended to be run at this point (maybe in Chapter 7, but that will be another story I am sure!).

Some useful hints - your modifications are not correct I think, according to what is in chapter 4. In particular, I think they may intend to use both IDENT and IDENTIFIER as separate symbols, just look at how they used side by side in the grammar and in the modification text. As such I defined a type for both and that resolves several issues (and opens others). When you make the modifications, look carefully at the surrounding context in the book and do it exactly as shown (which seems to me to be different than your posted code).

There are a couple of undefined variables - errors comes to mind. And types, types, types...

With those changes I find only one $x reference which seems to be wrong (but may be awaiting further modification in Chapter 7, very confusing).

Code:

exp : INT
 | IDENT { context_check( $1 ); } /* $2 in book */

I am less sure whether INT and INTEGER are intended to be separate symbols, but have left them both defined as they do not conflict with each other at this point.

Ah, conflicts... SURELY your bison does not silently build the code! Can you recheck that! I count 39 shift-reduce conflicts, mostly resulting from all the as yet undefined actions for all those exp terms!

And finally - the big answer you have been waiting for...

Code:

$ gcc lex.yy.c -lfl
/tmp/ccH6IRzd.o: In function `yylex':
/full/path/ch4.lex:36: undefined reference to `yylval'
collect2: ld returned 1 exit status

Look at that - it is a linker error, not a compiler error - it is defined in the header file, but there is no object code to link to! You have to compile it! Try this...

Code:

gcc lex.yy.c ch4.tab.c -lfl

So how does it run...? I leave that for another day as well!

Good luck!

dedec0 · 09-01-2016, 07:28 AM

Quote:

Originally Posted by astrogeek

First a personal comment - As this PDF, this alleged Flex/Bison "book" originated from Micro$oft I am inclined to think it is an example of them poisoning the FREE software well by providing examples that are so obscure, incomplete and badly written that they will discourage all who attempt to use them from ever trying to use FREE software again in the future!

Sheeeesh!!

We are not being fair to Microsoft in this discussion. I have thought about saying it before, but kept it because it did not seem necessary. I am not a fan of Microsoft also, but it has been doing a few good things toward the open source things - that I will not discuss or tell in this thread, please do not do it. All that Microsoft has done in this story is to distribute the file of this book. It is available in many other places as well, I chose its website because it seems more reliable, given the other choices I saw then. Check it yourselves: https://duckduckgo.com/html/?q=antho...bison+compiler.

This book is free: we can copy and distribute it as much as we want, no harm done to anyone. This is written in its pages. When the author, Anthony A. Aaby, wrote it, he was in USA, in the then called Walla Walla College (website was cs.wwc.edu, does not exist anymore). His email account is also written in the book: aabyan@wwc.edu. This account is not active anymore, I discovered this when I tried to contact him for the first "bigger" problems I had. This college is now an university, changed its name, he does not work there anymore. By finding and contacting them, they have told me most of this information. They were kind and helpful as they could, even offering me the contact of their Computer Science team to discuss anything - which was out of scope for me, I preferred to choose this forum.

There has been an initiative to make a Wikibook from this work. I think the idea is good, since the book has many details that seems incomplete. And the book ideas have a place to exist, just need some more work - partially done in this thread we are making.

Just to end this post with a good thought for everybody... a composer from my country says: "the best things in life are free".

dedec0 · 09-01-2016, 12:04 PM

Chapter 4 is still waiting for some more work (from me). I plan to do this in the next two days, I will make another post just for that.

While the discussion in the last posts were made, I have finished chapter 5. It just presents a few fairly simple ideas on optimization of the parse tree. But it does not present anything else. No code, just a few pseudo code transformations and some explanation where needed. The ideas are showing using a tree, sadly. We must get it ourselves.

I will not try to make some code to optimize now - not until I finish this book and know better how to use these tools, at least. =)

astrogeek · 09-01-2016, 02:56 PM

Sorry, it was not my intent to divert this thread into an anti-M$ rant. My comment was plainly labeled as personal opinion and kept brief - but my frustrations with the book demanded some vent at the time. My disdain for all things M$ is irreconcilable, we won't go there.

So with only the most brief response possible...

Quote:

Originally Posted by dedec0

We are not being fair to Microsoft in this discussion.

The M$ corporate has done immeasurable damage to all our lives, all our societies and all our futures. The only fairness will come when the individuals responsible for that behavior are held to account as the criminals they are, and their ill-gotten fortunes liquidated and distributed to the poor.

Quote:

Originally Posted by dedec0

This book is free: we can copy and distribute it as much as we want, no harm done to anyone.

That is entirely thanks to the author! And as I do not know the originally intended audience, I cannot say whether the book accomplished what the author intended or not - it may have been entirely successful in its intended purpose for all I know. But clearly that purpose was not focused on teaching Flex and Bison per se.

But the fact that it was chosen as a resource on the M$ site stains it... like a dentist passing out free candy! The candy itself is not evil, but the dentist's motives are necessarily open to question! That was the thought I expressed.

The best things are indeed FREE, as in FREEDOM! But do not confuse free of cost, or "open source" with FREEDOM!

That is enough... back to the grammar in another post...

sundialsvcs · 09-01-2016, 06:00 PM

Actually, "when human creative effort

meets the computer," Microsoft Corporation is in pretty much the same boat as the rest of us. In order to (profitably) produce products, they first have to make them work. Bison happens to be a technology that they use a lot, because it's a little bit more forgiving than Yacc. (And, due to Microsoft's long corporate history, they're "stuck" with some syntaxes for which Bison is better.)

So, in this case, I would regard their "corporate offering" simply at face value, and say, "thank you."

I consider "Microsoft Press" to be a superb technical publishing house, and I still consider their "Software Engineering Classics" boxed-set to be ... well ... "a classic."

No matter what you might think of the layers of mega-corporate bullsh*t mantle

that has been lathered upon Microsoft over so many years and by so many Wall Street investors, at the heart of the company there still beats the heart and soul of a group of people who have done some truly-magnificent things hacks ... successfully. (Even, dare I say it, "gracefully.")

Quote:

"Sonofab*tch ... Dammit!! ... I don't wanna say it 'cept I have to ... ... They a-r-e good! ... ... They are That good!!"

Yes, "still." Despise them if you want to, but, "they are where they are today" because ... because ... they earned it. (Aye, in spite of Wall Street.)

dedec0 · 09-03-2016, 04:46 AM

So I have made the partially unsatisfying steps (shown before) to compile chapter 4 files (also given above). It was not working as expected, I was using a correct Simple code - not! The grammar given in chapter 1 is not consistent with the lex and bison files (or parts of them) shown after that. It is obvious to see it, but I did not even considered or thought about checking the consistence of this detail.

A Simple program that satisfies the current compilation steps is:

Code:

 let integer trees, seedpackage. in 
    trees := 3;
    seedpackage := 17;
    while trees < 1000 do
	trees := trees + seedpackage;
    end;
    write trees;
 end

It is much different from the Simple program I wrote here before. It is more Complicated! xD

Now I am a bit puzzled by what is being considered from ch4.lex and from ch4.y, and what is wrong in them, for this execution. Some "obvious" comments would be nice. Some quick questions I have:

1. The lex file does not have tokens for +-*/^><= operators. They appear explicitly in bison file. I should create them, right? Would it be good to make a better scanner (more complete) and separate more clearly the scanner from the parser?

2. Bison file has a precedence for '='. It is different from ':=' (ASSGNOP).

Code:

 let integer a, b, c. in
   c := 3;
   a := b = c;
 end

Would it be the comparison operator that does that "==" does in C?

3. The bison file has the line %right '^ '. Note the space. Does a "^" followed by a space makes any sense? I am tempted to remove that space... both programs are accepted now, with the space in that line:

Code:

 let integer a,b,c. in
   a := b^ c;
 end

Code:

 let integer a,b,c. in
   a := b^c;
 end

4. In bison file, does the rule exp : exp '' exp, with two single quotes together, make sense?

5. Is the Simple language a creation of the book author? Have you ever seen it somewhere else? My searches had no other ocurrences.

6. Any other "hidden" things here?

dedec0 · 09-03-2016, 12:38 PM

Quote:

Originally Posted by dedec0

2. Bison file has a precedence for '='. It is different from ':=' (ASSGNOP).

Code:

 let integer a, b, c. in
   c := 3;
   a := b = c;
 end

Would it be the comparison operator that does that "==" does in C?

Yes. This was confirmed (written) elsewhere. It is intended do be used in conditionals (if, while), and not in an attribution, like above. The above code is accepted, but is not correct.

Quote:

Originally Posted by dedec0

4. In bison file, does the rule exp : exp '' exp, with two single quotes together, make sense?

They do not make sense. The bison file did not have the rule for the * operator... guess where it should be!

The other questions are still waiting answers...

astrogeek · 09-03-2016, 11:55 PM

Quote:

Originally Posted by dedec0

So I have made the partially unsatisfying steps (shown before) to compile chapter 4 files (also given above). It was not working as expected

I must ask the question, how are you expecting it to work at this point? Are you expecting it to be capable of processing "Simple" programs?

Quote:

Originally Posted by dedec0

I was using a correct Simple code - not! The grammar given in chapter 1 is not consistent with the lex and bison files (or parts of them) shown after that. It is obvious to see it, but I did not even considered or thought about checking the consistence of this detail.

No it is neither consistent, nor complete.

Quote:

Originally Posted by dedec0

Now I am a bit puzzled by what is being considered from ch4.lex and from ch4.y, and what is wrong in them, for this execution. Some "obvious" comments would be nice. Some quick questions I have:

1. The lex file does not have tokens for +-*/^><= operators. They appear explicitly in bison file. I should create them, right? Would it be good to make a better scanner (more complete) and separate more clearly the scanner from the parser?

Those are all handled by the 'any character' rule in the lexer.

Quote:

Originally Posted by dedec0

2. Bison file has a precedence for '='. It is different from ':=' (ASSGNOP).

Code:

 let integer a, b, c. in
   c := 3;
   a := b = c;
 end

Would it be the comparison operator that does that "==" does in C?

From the above usage it would be a comparison operator I think.

But I see no precedence set for it in the bison code...??

Quote:

Originally Posted by dedec0

3. The bison file has the line %right '^ '. Note the space. Does a "^" followed by a space makes any sense? I am tempted to remove that space... both programs are accepted now, with the space in that line:

Code:

 let integer a,b,c. in
   a := b^ c;
 end

Code:

 let integer a,b,c. in
   a := b^c;
 end

No, that is an extraneous space introduced in the copy paste. The 'ˆ' in the PDF is also not a caret character, it is unicode 0x02c6. You should also double check the rest as -,*,_, all quotes and ^ were not ASCII in all cases (also not consistent!).

The ONLY way that rule makes sense is to remove the space and replace the 0x02c6 with a real ASCII '^' (0x5e).

There were _many_ such cases in the PDF, so double check everything from your copy paste code...

It might also be that your local locale settings and editors affect how copy/paste translates those.

Quote:

Originally Posted by dedec0

4. In bison file, does the rule exp : exp '' exp, with two single quotes together, make sense?

No. It not a single error either - check the lines before and after it in Chapter 2 and Chapter 4 - they are not the same...

Quote:

Originally Posted by dedec0

5. Is the Simple language a creation of the book author? Have you ever seen it somewhere else? My searches had no other ocurrences.

6. Any other "hidden" things here?

I have never heard of a commonly known "Simple" language, but I have seen many examples referred to by their respective authors as "a simple language", even Levine uses the term in Flex & Bison (O'Reilly). So as far as I know there is no "Simple" language, it must be an invention of the author.

So may I ask, are you trying to write the wiki book that you mentioned?

dedec0 · 09-04-2016, 08:02 AM

I will answer each question or comment that you have made (without quoting, assuming it will be easier and faster to read it).

At this point (chapter 4) I expect it to accept Simple programs. It does not do anything. When the source is not recognized, an error is shown - and this fact made me see inconsistencies in grammar and definition pages of the book.

I know +-*/<>= are handled by the . in the lex file. The point I tried to make/ask is: they should have a token instead of being literally recognized in the parser.

For the = operator and its "precedence", I meant the lines:

Code:

%left '-' '+'
%left '*' '/'
%left '<' '>' '=' /* these where missing on the book, added */
%right '^'

The order of these lines and elements does not have a "last resort" consequence on their precedence?

For the "unicode or normal char" differences, I have tested most of the copied code. It should not have more of this.

So Simple is author's creation. I feel more free to change it in some details that seem bad or "not so simple".

I am not trying to write the wikibook now since I cannot completely understand and complete a considerable part of the book now. But I would do it otherwise. This thread, as it got, can probably help whoever tries that.

dedec0 · 09-09-2016, 06:36 AM

Chapter 5 presents some ideas for optimization, but it does not give a single example. May you help me getting a simple one to work? I believe that once this example is given, I should be able to add other optimizations to it.

The first step that I imagine is to make a full Simple language compiler, which is not what chapter 4 ended with (what I have now, described in posts before this one). Is this correct? What do you suggest?

astrogeek · 09-19-2016, 03:14 AM

Hi dedec0! Sorry to be so slow responding.

Partly, my delay is because I have been mostly unavailable... but partly it is because each time I do try to make sense of the (badly written and hopelessly incomplete IMO) book, it takes far too much time to fill in the mystery pieces and try to give a reasonable reply - so I end without being able to contribute anything helpful.

I have just completed that exercise yet again, and am inclined to make this my last trip around this particular hamster wheel.

Quote:

Originally Posted by dedec0

At this point (chapter 4) I expect it to accept Simple programs. It does not do anything. When the source is not recognized, an error is shown - and this fact made me see inconsistencies in grammar and definition pages of the book.

I am not sure that I understand what you are expressing here.

Are you saying that you expect it to accept - and process in some way - "Simple" programs, but you find that it does not do anything useful?

Or are you saying that it should accept the syntax without doing anything with it? This is loosely what it I would expect.

But as you have found, while it accepts user input strings (and does nothing with them), the "syntax" (i.e. grammar) it recognizes is very ambiguous (i.e. ill-defined), with 39 shift-reduce errors by my count - vagueness and errors are indeed the order of the day!

How to fix that? I cannot read the original author's mind so I cannot say how they intended to further develop this example. In as much as they did not complete the exercise themselves in this "book", it is kind of an open ended question.

Quote:

Originally Posted by dedec0

I know +-*/<>= are handled by the . in the lex file. The point I tried to make/ask is: they should have a token instead of being literally recognized in the parser.

That too is up to the author of the lexer and parser.

For myself, I almost always explicitly define every token and almost never rely on a "." handler to return the ASCII value as the token. On the other hand, Bison was specifically designed to not conflict with ASCII valued tokens just for this purpose, and either way they are just unique integers... so it is really down to your preference (the code author).

Quote:

Originally Posted by dedec0

For the = operator and its "precedence", I meant the lines:

Code:

%left '-' '+'
%left '*' '/'
%left '<' '>' '=' /* these where missing on the book, added */
%right '^'

The order of these lines and elements does not have a "last resort" consequence on their precedence?

Again, I am not really sure I understand your question.

The way Bison works is that symbols defined further down in the code have a higher precedence. If you do not assign any symbol's precedence explicitly, it will be assigned a precedence level based on where Bison first encounters it when processing the rules.

By explicitly assigning the associativity (%left, %right, %nonassoc), you are also declaring the precedence by the order of the lines. Symbols on the same line have the same precedence.

In the book, those symbols not declared will have a higher precedence based on their order of occurrance in the code, top to bottom.

Again, I have no idea what the author ultimately intended, whether this was an omission or intentional.

Quote:

Originally Posted by dedec0

So Simple is author's creation. I feel more free to change it in some details that seem bad or "not so simple".

I am not trying to write the wikibook now since I cannot completely understand and complete a considerable part of the book now. But I would do it otherwise. This thread, as it got, can probably help whoever tries that.

I think that to write the wikibook, you will first have to complete the language specification and the book itself. I am still of the opinion that it was rather obviously never completed and as such is not much useful as an accessible learning source. On the other hand, completing the book would indeed be a good, but difficult exercise for an advanced student.

Finally, you have asked about an example of the optimizations suggested in Chapter 5...

The text suggests changes in the parse tree (i.e. grammar specification) to optimize specific output code structures.

All I can say is that you would want to understand the parse tree generated by the existing rules for those cases, and modify them and likely add new nonterminals and rules to recognize those cases and lead to some desired result.

The rules as they exist do not lend themselves to that level of optimization (IMO), especially with existing ambiguities and without any action handling code yet written. Again, the author may have had something specific in mind, but I do not know what it was, and they did not elaborate...

Good luck!

dedec0 · 09-19-2016, 12:38 PM

No problem with your delay. Thank you for these efforts with my posts.

I will think more later, and (if and where still necessary) I will try to rewrite my questions.

One important point is that: the code I was able to use and/or improve from the book is not a full compiler, and (as consequence of this) it does not have any optimizations.

I would like to have an example compiler made with Flex and Bison that has all these characteristics. It does not need to be of the Simple language. It does not need (and should not) to be complex or big. But, as far as I have got until now, I could build one.

One point I tried to make and confirm with you is that some tasks happen in the parser "block", others in the scanner "block", which happens first. Why tokens for some of these symbols are not being tokenized? They should! (right?) I think it seems to bring a more clear division between each compiler phase, and so it is between some modifications I have made on my code copied from the book.