Lex & Yacc

Lex

• lex is a program (generator) that generates lexical analyzers, (widely used on Unix).
• It is mostly used with Yacc parser generator.
• Written by Eric Schmidt and Mike Lesk.
• It reads the input stream (specifying the lexical analyzer ) and outputs source code implementing the lexical analyzer in the C programming language.
• Lex will read patterns (regular expressions); then produces C code for a lexical analyzer that scans for identifiers.

​

Lex

• A simple pattern: letter(letter|digit)*
• Regular expressions are translated by lex to a computer program that mimics an FSA.
• This pattern matches a string of characters that begins with a single letter followed by zero or more letters or digits.

​

​

​

​

​

​

​

​

​

​

Lex

​

​

​

​

​

​

​

​

​

​

• Some limitations, Lex cannot be used to recognize nested structures such as parentheses, since it only has states and transitions between states.
• So, Lex is good at pattern matching, while Yacc is for more challenging tasks.

Lex

Pattern Matching Primitives

Lex

• Pattern Matching examples.

Lex

……..Definitions section……

%%

……Rules section……..

%%

……….C code section (subroutines)……..

​

• The input structure to Lex.

​

​

• Echo is an action and predefined macro in lex that writes code matched by the pattern.

​

​

​

​

Lex

Lex predefined variables.

Lex

• Whitespace must separate the defining term and the associated expression.
• Code in the definitions section is simply copied as-is to the top of the generated C file and must be bracketed with “%{“ and “%}” markers.
• substitutions in the rules section are surrounded by braces ({letter}) to distinguish them from literals.

Yacc

• Theory:
• Yacc reads the grammar and generate C code for a parser .

​

• Grammars written in Backus Naur Form (BNF) .

​

• BNF grammar used to express context-free languages .

​

• e.g. to parse an expression , do reverse operation( reducing the expression)

​

• This known as bottom-up or shift-reduce parsing .

​

• Using stack for storing (LIFO).

​

​

Yacc

• Input to yacc is divided into three sections.

​

​

... definitions ...

%%

... rules ...

%%

... subroutines ...

Yacc

• The definitions section consists of:
• token declarations .
• C code bracketed by “%{“ and “%}”.

​

• the rules section consists of:
• BNF grammar .

​

• the subroutines section consists of:
• user subroutines .

​

​

​

​

yacc& lex in Together

• The grammar:

program -> program expr | ε

expr -> expr + expr | expr - expr | id

​

• Program and expr are nonterminals.
• Id are terminals (tokens returned by lex) .

​

• expression may be :
• sum of two expressions .
• product of two expressions .
• Or an identifiers

Lex file

Yacc file

Linking lex&yacc

lex & yacc

Authors

• John R. Levine
• Tony Mason
• Doug Brown

The Simplest Lex Program

%%

. |\n ECHO;

%%

• The above lex program copies standard input to its standard output.
• .(period)->matches any single character other than newline.
• \n ->matches newline character.

• It acts very much like the UNIX cat command run with no arguments.
• The special action ECHO prints the matched pattern on output, copying any

punctuations or other characters.

​

Recognizing Words with Lex

Word recognizer:

%{

/* The sample program demonstrates a verb or not a verb

*/

%}

%%

[\t]+ /* ignore whitespace*/;

is |

am |

are |

were |

was |

be |

being |

been |

do |

does |

can |

could |

has |

have |

had |

go { printf ("%s: is a verb\n”, yytext) ; }

[a-zA-Z]+ { printf("%s: is not a verb\n”, yytext); }

. | \n { ECHO; /* normal default anyway */ }

%%

main ( )

{

yylex( );

}

Input: did i have fun?

Output: did:is a verb

i: is not a verb

have: is a verb

fun:is not a verb

?

• If the input matches any of the verbs in the list.Once we recognize a verb we execute the action ,a C printf state.
• yytext contains text that matched the pattern

• "[a-zA-Z]+ : it indicates any alphabetic string with at least one character.
• "-“: it denotes a range of characters beginning with the character to the left of the "-" and ending with the character to its right.

Symbol Tables

• A data structure used by compiler to keep track of identifiers used in the source program called as Symbol Table.
• Symbol table is a table of words with common structure used in lex and yacc

applications.

• Symbol table is a compile time data structure and not used at run time.
• C Compilers stores variables,structure names,labels,enumeration tags and other

names used in program in its symbol table.

• The possible entries in symbol table are

1.type of symbol

2.variable name or type

3.reserve word

4.constant name

5.declaration scope

• Symbol table is concerned with storing identifiers and their attributes.

​

• Symbol table is more required for semantic checking to check whether

1.variable assigned before referenced.

2.variable not declared multiple times.

Example: Lexer with symbol table

% {

/*

* Word recognizer with a symbol table.

*/

%}

​

Enum {

LOOKUP=0, /* default - looking rather than defining. */

VERB,

ADJ,

ADV,

NOUN,

PREP,

PRON,

CONJ,

};

int state;

int add_word(int type, char *word) ;

int lookup_word (char *word) ;

%}

add_word()->puts new word to symbol table.

lookup_word()->looks up a word which should already be entered.

​

Grammars

• A Sequence of tokens needs to be recognized and action taken.
• The description of such a set of actions called grammar.
• Lets consider example of simple sentence type

noun verb

noun verb noun

The notation for describing grammar is->

​

Which means particular set of tokens can be replaced by new symbol .*

subject->noun/pronoun

indicates subject can either be noun or pronoun

object->noun

Sentence->subject verb object

Example: teacher teaches students.

Parser-Lexer Communication

• A lex scanner and yacc parser used together called lexer-parser communication.
• Parser calls lexer yylex() when it needs a token from input.
• Lexer scan through input recognizing tokens returns tokens to parser.
• Parser is higher level routine.
• In most of programming language the parser doesnot want comments and whitespaces.

• Lex produces function called yylex()
• Yacc produces function called yyparse()

A Yacc Parser(Yet Another Compiler Compiler)

The structure of a yacc parser is similar to that of a lex lexer. First section, the definition section, has a literal code block, enclosed in "%{" and "%}". We use it here for a C comment (as with lex, C comments belong inside C code blocks, at least within the definition section) and a single include file.

Then come definitions of all the tokens we expect to receive from the lexical analyzer.

Universal custom dictates that token names be all uppercase and other names in the parser mostly or entirely lowercase.

The first %% indicates the beginning of the rules section. The second %% indicates the end of the rules and the beginning of the user subroutines section.

The most important subroutine is main() which repeatedly calls yyparse() until the lexer's input file runs out.

The routine yyparse() is the parser generated by yacc, so our main program repeatedly tries to parse sentences until the input runs out.Yacc is a tool for automatic generation of

parser.

The Rules Section

The rules section describes the actual grammar as a set of production rules or simply rules. (Some people also call them productions.) Each rule consists of a single name on the left-hand side of the ":" operator, a list of symbols and action code on the right-hand side, and a semicolon indicating the

end of the rule. By default, the first rule is the highest-level rule.

​

​

That is, the parser attempts to find a list of tokens which match this initial rule, or

more commonly, rules found from the initial rule. The expression on the right-hand side of the rule is a list of zero or more names. A typical simple rule has a single symbol on the right-hand side as in the object rule which is defined to be a NOUN. The symbol on the left-hand side of the rule can

​

then be used like a token in other rules.

Running Lex and Yacc

• Lex program

$ gedit filename –l

type Pgm & save

$ lex filename.l

$ cc lex.yy.c -ll

$ ./a.out

​

Executing lex and Yacc together

$ gedit filename.l

$ gedit filename.y

$ lex filename.l

$ yacc –d filename.y

$ cc lex.yy.c y.tab.c -ll -ly

$ ./a.out

​

Lex vs. Hand-written Lexers

• Writing a lexer in C is so easy there is no point in going to the effort to learn lex.
• Lexer written in C is suitable for simple command language that handles commands,numbers,strings and newlines ignoring whitespaces and comments.
• The program written in C takes 3 times more to debug compared to program in lex.

• Given the rule of thumb the number of bugs in a program is roughly proportional

to its length.

For example program refer text book.

​

Regular Expressions

• Regular expressions are widely used within the UNIX environment and lex uses a rich regular expression.
• A regular expression is a pattern description using a "meta" language, a language used to describe particular patterns of interest.
• The characters used in this metalanguage are part of the standard ASCII character set

​