lex and yacc (symbol table generation)

Question

I am new to lex and yacc and compiler design. I would like to know at which phase(lexical, syntactical or any other phase) and how the symbol table is generated?

Can I have a brief description of y.output file which is generated by giving -v option to yacc.I tried to looking into it but didn't get much info.

Could I know the other applications where lex and yacc are used apart from compiler designs.

Answer 1

A symbol table is a global data structure that can be used in all stages/phases/passes of a compiler. This means that it can be used/accessed from both the lex and yacc generated components.

It is conventional to access the symbol table entry from the lexical analyser when it finds a token that would be stored in the table, such as an identifier, it can find the entry and update it with information only available to the lexer like line number and character position and it can also store the lexeme value if it is not already there. The symbol table pointer can now be returned in the lval of the token.

Some people prefer to return a pointer to the lexeme itself (as the lval) from the lexer to the parser and do the initial symbol table access there. This has an advantage that the symbol table does not have to be visible to the lexer, but has the disadvantage that lexer information as described above may no longer be available to store with the symbol. It often has the disadvantage of making the parser actions from yacc a little more "busy" as they then may be involved in managing the symbol table as well as the parse tree.

The symbol table entry will be further updated in later phases of the compiler, such as a semantic walk of the parse tree which can annotate the symbol entries with type information and flag undeclared objects and the like. The symbol table will be used again during target code generation when target specific information may be stored or needed, and again during optimisation when variables usage may be examined or even optimised away.

The symbol table is a data structure that you the compiler writer create for yourself. There is no feature of lex or yacc that does it for you. It is generated as and when any code you write creates it!

The y.output file has nothing to do with symbol tables. It is a record of how yacc converted the context free grammar into a parse table. It is useful when you have an ambiguous grammar and want to know what rules are causing the shift/reduce or reduce/reduce errors when debugging your grammar.

The last part of the question, what uses do these tool have? lex is a tool that generates code for a state machine that recognises the patterns you specified. It does not have to be used in writing compilers. One interesting use is in handling networking protocols that can be processed by a state machine, such as TCP/IP datagrams and so forth. Similarly, yacc is used in matching sequences that are described by context free grammars. These do not have to be programs, but could be other complex sequences of symbols, fields or data items. They are just normally pieces of text, and that is the orthodox use of the tool.

These parts of your question really sound like the kind of exam question that someone might write for students who have attended a course in compilers!