{"id":145,"date":"2018-07-20T05:15:29","date_gmt":"2018-07-20T05:15:29","guid":{"rendered":"http:\/\/csp10.epgpbooks.inflibnet.ac.in\/?post_type=chapter&#038;p=145"},"modified":"2018-07-20T05:15:56","modified_gmt":"2018-07-20T05:15:56","slug":"lexical-analyzer-generator","status":"publish","type":"chapter","link":"https:\/\/ebooks.inflibnet.ac.in\/csp10\/chapter\/lexical-analyzer-generator\/","title":{"rendered":"Lexical Analyzer Generator"},"content":{"raw":"This module discusses the core issues in designing a lexical analyzer generator from basis or using a tool. The basics of LEX tool are also discussed.\r\n\r\n&nbsp;\r\n\r\n<strong>8.1 Need for a Tool<\/strong>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">The lexical analysis phase of the compiler is machine independent. It comes under the analysis phase. The lexical analysis phase needs to tokenize the input string and hence it is source language dependent. The lexical analyzer needs to define patterns for all programming constructs of the input language. Hence, designing a lexical analyzer from the scratch is difficult. On the other hand, if there is a tool that can handle these variations in source language, then designing the lexical analysis phase would be easier.<\/p>\r\n&nbsp;\r\n\r\n<strong>8.2 Lexical Analyzer Generator Tool<\/strong>\r\n\r\n&nbsp;\r\n\r\nLexical Analyzer Generator is typically implemented using a tool. There are some standard tools available in the UNIX environment. Some of the standard tools are\r\n<ul>\r\n \t<li style=\"text-align: justify\">LEX \u2013 it helps in writing programs whose flow of control is regulated by the various definitions of regular expressions in the input stream. The wrapper programming language is C.<\/li>\r\n \t<li style=\"text-align: justify\">FLEX \u2013 It is a faster lexical analyzer tool. This is also a C language version of the LEX tool.<\/li>\r\n \t<li style=\"text-align: justify\">JLEX \u2013 This is a Java version of LEX tool.<\/li>\r\n \t<li><img class=\"size-full wp-image-146 aligncenter\" src=\"http:\/\/csp10.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/50\/2018\/07\/Untitled-77.png\" alt=\"\" width=\"607\" height=\"341\" \/>\r\n<div>\r\n<p style=\"text-align: justify\">The input will be a source file with a \u2015.l\u2016 extension. This will be compiled by a Lex compiler and the output of this compiler will be a source file in C named as \u2015lex.yy.c\u2016. This can be compiled using a C compiler to get the desired output.<\/p>\r\n&nbsp;\r\n\r\n<strong>8.3 Components of a LEX program<\/strong>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">A LEX program typically consists of three parts: An initial declaration section, a middle set of translation rules and the last section that consists of other auxiliary procedures. The \u2015%%\u2016 acts as a delimiter which separates the declaration section from the translation rules section and the translation rules section from the auxiliary procedures section. A program may miss the declaration section but the delimiter is mandatory.<\/p>\r\n&nbsp;\r\n\r\ndeclaration\r\n\r\n%%\r\n\r\ntranslation rules\r\n\r\n%%\r\n\r\nauxiliary procedures\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">In the declaration section, declarations and initialization of variables take place. In the translation rules section, regular expressions to match tokens along with the necessary actions are defined. The auxiliary procedures section consists of a main function corresponding to a C program and any other functions that are required in the auxiliary procedures section.<\/p>\r\n&nbsp;\r\n\r\n<strong>8.3.1 Declaration<\/strong>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">In the declaration section a regular expression can be defined. Following is an example of declaration section. Each statement has two components: a name and a regular expression that is used to denote the name.<\/p>\r\n&nbsp;\r\n\r\n1.\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 delim [\\t\\n]\r\n\r\n2.\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 ws{delim}+\r\n\r\n3.\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 letter\u00a0 [A-Za-z]\r\n\r\n4.\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 digit\u00a0\u00a0 [0-9]\r\n\r\n5.\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 id{letter}({letter}|{digit})*\r\n\r\n&nbsp;\r\n\r\nTable 8.1 summarizes the operators and special characters used in the regular expressions which are part of the declaration and translation rules section.\r\n\r\n<\/div>\r\n<div>\r\n\r\nTable 8.1 Meta Characters\r\n\r\n&nbsp;\r\n<table class=\"aligncenter\" border=\"1\">\r\n<tbody>\r\n<tr>\r\n<td style=\"width: 164.063px\"><strong>Meta Character<\/strong><\/td>\r\n<td style=\"width: 480.063px\"><strong>Match<\/strong><\/td>\r\n<\/tr>\r\n<tr>\r\n<td style=\"width: 164.063px\">.<\/td>\r\n<td style=\"width: 480.063px\">Any character except new line<\/td>\r\n<\/tr>\r\n<tr>\r\n<td style=\"width: 164.063px\">\\n<\/td>\r\n<td style=\"width: 480.063px\">newline<\/td>\r\n<\/tr>\r\n<tr>\r\n<td style=\"width: 164.063px\">*<\/td>\r\n<td style=\"width: 480.063px\">zero or more copies of the preceding expression<\/td>\r\n<\/tr>\r\n<tr>\r\n<td style=\"width: 164.063px\">+<\/td>\r\n<td style=\"width: 480.063px\">one or more copies of the preceding expression<\/td>\r\n<\/tr>\r\n<tr>\r\n<td style=\"width: 164.063px\">?<\/td>\r\n<td style=\"width: 480.063px\">zero or one copy of the preceding expression<\/td>\r\n<\/tr>\r\n<tr>\r\n<td style=\"width: 164.063px\">^<\/td>\r\n<td style=\"width: 480.063px\">beginning of line<\/td>\r\n<\/tr>\r\n<tr>\r\n<td style=\"width: 164.063px\">$<\/td>\r\n<td style=\"width: 480.063px\">end of line<\/td>\r\n<\/tr>\r\n<tr>\r\n<td style=\"width: 164.063px\">a|b<\/td>\r\n<td style=\"width: 480.063px\">a or b<\/td>\r\n<\/tr>\r\n<tr>\r\n<td style=\"width: 164.063px\">(ab)+<\/td>\r\n<td style=\"width: 480.063px\">one or more copies of ab (grouping)<\/td>\r\n<\/tr>\r\n<tr>\r\n<td style=\"width: 164.063px\">\"a+b\"<\/td>\r\n<td style=\"width: 480.063px\">literal \"a+b\" (C escapes still work)<\/td>\r\n<\/tr>\r\n<tr>\r\n<td style=\"width: 164.063px\">[ ]<\/td>\r\n<td style=\"width: 480.063px\">character class<\/td>\r\n<\/tr>\r\n<\/tbody>\r\n<\/table>\r\n&nbsp;\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">In addition, the declaration section may also contain some local variable declarations and definitions which can be modified in the subsequent sections.<\/p>\r\n&nbsp;\r\n\r\n<strong>8.3.2 Translation Rules<\/strong>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">This is the second section of the LEX program after the declarations. The declarations section is separated from the Translation Rules section by means of the \u2015%%\u2016 delimiter. Here, each statement consists of two components: a pattern and an action. The pattern is matched with the input. If there is a match of pattern, the action listed against the pattern is carried out. Thus the LEX tool can be looked upon as a rule based programming language. The following is an example of patterns p1, p2\u2026pn and their corresponding actions 1 to n.<\/p>\r\n&nbsp;\r\n\r\np1\u00a0\u00a0 {action1} \/*p\u2014pattern (Regular exp) *\/\r\n\r\n&nbsp;\r\n\r\n\u2026\r\n\r\n&nbsp;\r\n\r\npn\u00a0\u00a0\u00a0 {actionn}\r\n<p style=\"text-align: justify\">For example, if the keyword IF is to be returned as a token for a match with the input string \u2015if\u2016 then the translation rule is defined as<\/p>\r\n&nbsp;\r\n\r\n{if}\u00a0\u00a0\u00a0 {return(IF);}\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">The \u2015;\u2016 at the end of the (IF) indicates end of the first statement of an action and the entire sequence of actions is available between a pair of parenthesis. If the action has been written in multiple lines then the continuation character needs to be used. Similarly the following is an example for an identifier \u2015id\u2016, where the usage of \u2015id\u2016 is already stated in the first \u2015declaration\u2016 section.<\/p>\r\n\r\n<\/div>\r\n<div>\r\n\r\n{id}\u00a0\u00a0 {yylval=install_id();return(ID);}\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">In the above statement, when encountering an identifier, two actions need to be taken. The first one is call install_id() function and assign it to yylval and the second one is a return statement.<\/p>\r\n&nbsp;\r\n\r\n<strong>8.3.3 Auxiliary procedures<\/strong>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">This section is separated from the translation rules section using the delimiter \u2015%%\u2016. In this section, the C program\u2019s main function is declared and the other necessary functions also defined. In the example defined in translation rules section, the function install_id() is a procedure used to install the lexeme, whose first character is pointed by yytext and length is provided by yyleng which are inserted into the symbol table and return a pointer pointing to the beginning of the lexeme.<\/p>\r\n&nbsp;\r\n\r\ninstall_id() {\r\n\r\n&nbsp;\r\n\r\n}\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">The functionality of install_id can be written separately or combined with the main function. The functions yytext ( ) and yyleng( ) are lex commands to indicate the text of the input and the length of the string.<\/p>\r\n&nbsp;\r\n\r\n<strong>8.4 Example LEX program<\/strong>\r\n\r\n&nbsp;\r\n\r\nThe following LEX program is used to count the number of lines in the input data stream.\r\n\r\n&nbsp;\r\n\r\n1.\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 int num_lines = 0;\r\n\r\n2.\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 %%\r\n\r\n3.\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 \\n++num_lines;\r\n\r\n4.\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 .;\r\n\r\n5.\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 %%\r\n\r\n6.\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 main()\r\n\r\n7.\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 {\u00a0 yylex();\r\n\r\n8.\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 printf( \"# of lines = %d\\n\", num_lines); }\r\n\r\n&nbsp;\r\n\r\n<strong>Example 8.1 LEX program to count the number of lines<\/strong>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">Line 1 of this program belongs to the declaration section and declares an integer variable num_lines and initializes it to 0 and this concludes the first section. In the translation rules section the pattern in \u2015\\n\u2016 which is defined in line 3 needs to be matched with the action, incrementing the variable num_lines. This statement indicates whenever a new line is encountered which is defined by \\n, the line number is incremented. The third section is from line numbers 6 to 8. yylex( ) points to the text defined in the input stream and as long as data exists in the input, the line numbers are counted and printed in Line 8.<\/p>\r\n\r\n<\/div>\r\n<div>\r\n\r\n&nbsp;\r\n\r\nExample 8.2 is an extension of example 8.1 where number of characters, words and lines are counted.\r\n\r\n&nbsp;\r\n\r\n1.\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 %{ int nchar, nword, nline; %}\r\n\r\n2.\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 %%\r\n\r\n3.\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 \\n { nline++; nchar++; }\r\n\r\n4.\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 [^ \\t\\n]+ { nword++, nchar += yyleng; } . { nchar++; }\r\n\r\n5.\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 %%\r\n\r\n6.\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 int main(void)\r\n\r\n7.\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 { yylex();\r\n\r\n8.\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 printf(\"%d\\t%d\\t%d\\n\", nchar, nword, nline);\r\n\r\n9.\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 return 0; }\r\n\r\n&nbsp;\r\n\r\n<strong>Example 8.2 LEX program to count number of lines, characters and words<\/strong>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">In this example \u2015\\n\u2016 is mapped to increment the number of characters and number of lines, while \\t, a tab space is used to increment the number of words and number of characters which is defined in line numbers 3 and 4. Lines 6 to 9 represent the main function, which uses yylex to point to the text and processes it to count the number of lines, characters and words.<\/p>\r\n&nbsp;\r\n\r\nTable 8.2 is a summary of some of the yy() commands that can be used in LEX program.\r\n\r\n&nbsp;\r\n<table class=\"aligncenter\" border=\"1\">\r\n<tbody>\r\n<tr>\r\n<td style=\"width: 202.063px\"><\/td>\r\n<td style=\"width: 442.063px\"><strong>Table 8.2<\/strong><\/td>\r\n<\/tr>\r\n<tr>\r\n<td style=\"width: 202.063px\"><\/td>\r\n<td style=\"width: 442.063px\"><\/td>\r\n<\/tr>\r\n<tr>\r\n<td style=\"width: 202.063px\"><strong>Name<\/strong><\/td>\r\n<td style=\"width: 442.063px\"><strong>Function<\/strong><\/td>\r\n<\/tr>\r\n<tr>\r\n<td style=\"width: 202.063px\">int yylex(void)<\/td>\r\n<td style=\"width: 442.063px\">call to invoke lexer, returns token<\/td>\r\n<\/tr>\r\n<tr>\r\n<td style=\"width: 202.063px\">char *yytext<\/td>\r\n<td style=\"width: 442.063px\">pointer to matched string<\/td>\r\n<\/tr>\r\n<tr>\r\n<td style=\"width: 202.063px\">yyleng<\/td>\r\n<td style=\"width: 442.063px\">length of matched string<\/td>\r\n<\/tr>\r\n<tr>\r\n<td style=\"width: 202.063px\">yylval<\/td>\r\n<td style=\"width: 442.063px\">value associated with token<\/td>\r\n<\/tr>\r\n<tr>\r\n<td style=\"width: 202.063px\">int yywrap(void)<\/td>\r\n<td style=\"width: 442.063px\">wrapup, return 1 if done, 0 if not done<\/td>\r\n<\/tr>\r\n<tr>\r\n<td style=\"width: 202.063px\">FILE *yyout<\/td>\r\n<td style=\"width: 442.063px\">output file<\/td>\r\n<\/tr>\r\n<tr>\r\n<td style=\"width: 202.063px\">FILE *yyin<\/td>\r\n<td style=\"width: 442.063px\">input file<\/td>\r\n<\/tr>\r\n<tr>\r\n<td style=\"width: 202.063px\">INITIAL<\/td>\r\n<td style=\"width: 442.063px\">initial start condition<\/td>\r\n<\/tr>\r\n<tr>\r\n<td style=\"width: 202.063px\">BEGIN condition<\/td>\r\n<td style=\"width: 442.063px\">switch start condition<\/td>\r\n<\/tr>\r\n<tr>\r\n<td style=\"width: 202.063px\">ECHO<\/td>\r\n<td style=\"width: 442.063px\">write matched string<\/td>\r\n<\/tr>\r\n<\/tbody>\r\n<\/table>\r\n&nbsp;\r\n\r\n&nbsp;\r\n\r\nThe syntax and compilation procedure of FLEX program is the same as that of the LEX program.\r\n\r\n<\/div>\r\n<div>\r\n\r\n<strong>8.4 JLEX program<\/strong>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">A typical JLEX program also consists of three parts. In the case of JLEX program, the organization is slightly different. The first section represents the user code which is later copied directly as a Java file. The second section consists of JLEX directives, where macros and other state names are typically defined. Here again, \u2015%%\u2016 is used as a delimiter to separate one section from the other. The third section consists of the translation rules that define regular expressions along with the necessary actions. The user code is copied to a java file and a JAVA compiler is used instead of a C compiler of the LEX program to compile and execute the JLEX program. The following is a simple layout of a JLEX file.<\/p>\r\n&nbsp;\r\n\r\nUser code\r\n\r\n<strong>%%<\/strong>\r\n\r\nJLex directives\r\n\r\n<strong>%%<\/strong>\r\n\r\nLexical analysis rules\r\n\r\n&nbsp;\r\n\r\nExample 8.3 is a JLEX program to count the number of lines in an input document.\r\n\r\n&nbsp;\r\n\r\n1.\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 import java_cup.runtime.*;\r\n\r\n2.\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 %%\r\n\r\n3.\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 %cup\r\n\r\n4.\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 %{\r\n\r\n5.\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 private int lineCounter = 0;\r\n\r\n6.\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 %}\r\n\r\n7.\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 %eofval{\r\n\r\n8.\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 System.out.println(\"line number=\" + lineCounter);\r\n\r\n9.\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 return new Symbol(sym.EOF);\r\n\r\n10.\u00a0\u00a0 %eofval}\r\n\r\n11.\u00a0\u00a0 NEWLINE=\\n\r\n\r\n12.\u00a0\u00a0 %%\r\n\r\n13.\u00a0\u00a0 {NEWLINE} {\r\n\r\n14.\u00a0\u00a0 lineCounter++;\r\n\r\n15.\u00a0\u00a0 }\r\n\r\n16.\u00a0\u00a0 [^{NEWLINE}] { }\r\n\r\n&nbsp;\r\n\r\n<strong>Example8.3 Sample JLEX program<\/strong>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">In example 8.3, line number 1 indicates the user code which gets copied to the java file. %cup is used to activate the Java CUP compatibility that helps conform to the java_cup.runtime and<\/p>\r\n\r\n<\/div>\r\n<p style=\"text-align: justify\">initiates the scanner. The Java CUP compatibility is turned off by default and hence every JLEX program needs to get activate as the first step. %eofval is used to indicate \u2015end of value\u2016 of the input. The variable line number is incremented for every NEWLINE encountered in line number<\/p>\r\n\r\n<ol start=\"14\">\r\n \t<li style=\"text-align: justify\">NEWLINE is a name given to the \u2015\\n\u2016 character which indicates the encounter of a new line. This is again a rule based programming language and hence does not obey the flow of a structured programming language.<\/li>\r\n<\/ol>\r\n&nbsp;\r\n\r\n<strong>Summary<\/strong>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">This module discussed the use of tools LEX and JLEX for tokenizing the input. Designing and implementing the lexical phase of the compiler is difficult and hence tools can be used to do the job of tokenizing using a rule based programming language. The tools use regular expressions to define the pattern and a corresponding action. When the regular expression matches a pattern, the defined action is used to perform a task.<\/p>\r\n<\/li>\r\n<\/ul>","rendered":"<p>This module discusses the core issues in designing a lexical analyzer generator from basis or using a tool. The basics of LEX tool are also discussed.<\/p>\n<p>&nbsp;<\/p>\n<p><strong>8.1 Need for a Tool<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">The lexical analysis phase of the compiler is machine independent. It comes under the analysis phase. The lexical analysis phase needs to tokenize the input string and hence it is source language dependent. The lexical analyzer needs to define patterns for all programming constructs of the input language. Hence, designing a lexical analyzer from the scratch is difficult. On the other hand, if there is a tool that can handle these variations in source language, then designing the lexical analysis phase would be easier.<\/p>\n<p>&nbsp;<\/p>\n<p><strong>8.2 Lexical Analyzer Generator Tool<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p>Lexical Analyzer Generator is typically implemented using a tool. There are some standard tools available in the UNIX environment. Some of the standard tools are<\/p>\n<ul>\n<li style=\"text-align: justify\">LEX \u2013 it helps in writing programs whose flow of control is regulated by the various definitions of regular expressions in the input stream. The wrapper programming language is C.<\/li>\n<li style=\"text-align: justify\">FLEX \u2013 It is a faster lexical analyzer tool. This is also a C language version of the LEX tool.<\/li>\n<li style=\"text-align: justify\">JLEX \u2013 This is a Java version of LEX tool.<\/li>\n<li><img loading=\"lazy\" decoding=\"async\" class=\"size-full wp-image-146 aligncenter\" src=\"http:\/\/csp10.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/50\/2018\/07\/Untitled-77.png\" alt=\"\" width=\"607\" height=\"341\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-content\/uploads\/sites\/50\/2018\/07\/Untitled-77.png 607w, https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-content\/uploads\/sites\/50\/2018\/07\/Untitled-77-300x169.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-content\/uploads\/sites\/50\/2018\/07\/Untitled-77-65x37.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-content\/uploads\/sites\/50\/2018\/07\/Untitled-77-225x126.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-content\/uploads\/sites\/50\/2018\/07\/Untitled-77-350x197.png 350w\" sizes=\"auto, (max-width: 607px) 100vw, 607px\" \/>\n<div>\n<p style=\"text-align: justify\">The input will be a source file with a \u2015.l\u2016 extension. This will be compiled by a Lex compiler and the output of this compiler will be a source file in C named as \u2015lex.yy.c\u2016. This can be compiled using a C compiler to get the desired output.<\/p>\n<p>&nbsp;<\/p>\n<p><strong>8.3 Components of a LEX program<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">A LEX program typically consists of three parts: An initial declaration section, a middle set of translation rules and the last section that consists of other auxiliary procedures. The \u2015%%\u2016 acts as a delimiter which separates the declaration section from the translation rules section and the translation rules section from the auxiliary procedures section. A program may miss the declaration section but the delimiter is mandatory.<\/p>\n<p>&nbsp;<\/p>\n<p>declaration<\/p>\n<p>%%<\/p>\n<p>translation rules<\/p>\n<p>%%<\/p>\n<p>auxiliary procedures<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">In the declaration section, declarations and initialization of variables take place. In the translation rules section, regular expressions to match tokens along with the necessary actions are defined. The auxiliary procedures section consists of a main function corresponding to a C program and any other functions that are required in the auxiliary procedures section.<\/p>\n<p>&nbsp;<\/p>\n<p><strong>8.3.1 Declaration<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">In the declaration section a regular expression can be defined. Following is an example of declaration section. Each statement has two components: a name and a regular expression that is used to denote the name.<\/p>\n<p>&nbsp;<\/p>\n<p>1.\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 delim [\\t\\n]<\/p>\n<p>2.\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 ws{delim}+<\/p>\n<p>3.\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 letter\u00a0 [A-Za-z]<\/p>\n<p>4.\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 digit\u00a0\u00a0 [0-9]<\/p>\n<p>5.\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 id{letter}({letter}|{digit})*<\/p>\n<p>&nbsp;<\/p>\n<p>Table 8.1 summarizes the operators and special characters used in the regular expressions which are part of the declaration and translation rules section.<\/p>\n<\/div>\n<div>\n<p>Table 8.1 Meta Characters<\/p>\n<p>&nbsp;<\/p>\n<table class=\"aligncenter\">\n<tbody>\n<tr>\n<td style=\"width: 164.063px\"><strong>Meta Character<\/strong><\/td>\n<td style=\"width: 480.063px\"><strong>Match<\/strong><\/td>\n<\/tr>\n<tr>\n<td style=\"width: 164.063px\">.<\/td>\n<td style=\"width: 480.063px\">Any character except new line<\/td>\n<\/tr>\n<tr>\n<td style=\"width: 164.063px\">\\n<\/td>\n<td style=\"width: 480.063px\">newline<\/td>\n<\/tr>\n<tr>\n<td style=\"width: 164.063px\">*<\/td>\n<td style=\"width: 480.063px\">zero or more copies of the preceding expression<\/td>\n<\/tr>\n<tr>\n<td style=\"width: 164.063px\">+<\/td>\n<td style=\"width: 480.063px\">one or more copies of the preceding expression<\/td>\n<\/tr>\n<tr>\n<td style=\"width: 164.063px\">?<\/td>\n<td style=\"width: 480.063px\">zero or one copy of the preceding expression<\/td>\n<\/tr>\n<tr>\n<td style=\"width: 164.063px\">^<\/td>\n<td style=\"width: 480.063px\">beginning of line<\/td>\n<\/tr>\n<tr>\n<td style=\"width: 164.063px\">$<\/td>\n<td style=\"width: 480.063px\">end of line<\/td>\n<\/tr>\n<tr>\n<td style=\"width: 164.063px\">a|b<\/td>\n<td style=\"width: 480.063px\">a or b<\/td>\n<\/tr>\n<tr>\n<td style=\"width: 164.063px\">(ab)+<\/td>\n<td style=\"width: 480.063px\">one or more copies of ab (grouping)<\/td>\n<\/tr>\n<tr>\n<td style=\"width: 164.063px\">&#8220;a+b&#8221;<\/td>\n<td style=\"width: 480.063px\">literal &#8220;a+b&#8221; (C escapes still work)<\/td>\n<\/tr>\n<tr>\n<td style=\"width: 164.063px\">[ ]<\/td>\n<td style=\"width: 480.063px\">character class<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">In addition, the declaration section may also contain some local variable declarations and definitions which can be modified in the subsequent sections.<\/p>\n<p>&nbsp;<\/p>\n<p><strong>8.3.2 Translation Rules<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">This is the second section of the LEX program after the declarations. The declarations section is separated from the Translation Rules section by means of the \u2015%%\u2016 delimiter. Here, each statement consists of two components: a pattern and an action. The pattern is matched with the input. If there is a match of pattern, the action listed against the pattern is carried out. Thus the LEX tool can be looked upon as a rule based programming language. The following is an example of patterns p1, p2\u2026pn and their corresponding actions 1 to n.<\/p>\n<p>&nbsp;<\/p>\n<p>p1\u00a0\u00a0 {action1} \/*p\u2014pattern (Regular exp) *\/<\/p>\n<p>&nbsp;<\/p>\n<p>\u2026<\/p>\n<p>&nbsp;<\/p>\n<p>pn\u00a0\u00a0\u00a0 {actionn}<\/p>\n<p style=\"text-align: justify\">For example, if the keyword IF is to be returned as a token for a match with the input string \u2015if\u2016 then the translation rule is defined as<\/p>\n<p>&nbsp;<\/p>\n<p>{if}\u00a0\u00a0\u00a0 {return(IF);}<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">The \u2015;\u2016 at the end of the (IF) indicates end of the first statement of an action and the entire sequence of actions is available between a pair of parenthesis. If the action has been written in multiple lines then the continuation character needs to be used. Similarly the following is an example for an identifier \u2015id\u2016, where the usage of \u2015id\u2016 is already stated in the first \u2015declaration\u2016 section.<\/p>\n<\/div>\n<div>\n<p>{id}\u00a0\u00a0 {yylval=install_id();return(ID);}<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">In the above statement, when encountering an identifier, two actions need to be taken. The first one is call install_id() function and assign it to yylval and the second one is a return statement.<\/p>\n<p>&nbsp;<\/p>\n<p><strong>8.3.3 Auxiliary procedures<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">This section is separated from the translation rules section using the delimiter \u2015%%\u2016. In this section, the C program\u2019s main function is declared and the other necessary functions also defined. In the example defined in translation rules section, the function install_id() is a procedure used to install the lexeme, whose first character is pointed by yytext and length is provided by yyleng which are inserted into the symbol table and return a pointer pointing to the beginning of the lexeme.<\/p>\n<p>&nbsp;<\/p>\n<p>install_id() {<\/p>\n<p>&nbsp;<\/p>\n<p>}<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">The functionality of install_id can be written separately or combined with the main function. The functions yytext ( ) and yyleng( ) are lex commands to indicate the text of the input and the length of the string.<\/p>\n<p>&nbsp;<\/p>\n<p><strong>8.4 Example LEX program<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p>The following LEX program is used to count the number of lines in the input data stream.<\/p>\n<p>&nbsp;<\/p>\n<p>1.\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 int num_lines = 0;<\/p>\n<p>2.\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 %%<\/p>\n<p>3.\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 \\n++num_lines;<\/p>\n<p>4.\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 .;<\/p>\n<p>5.\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 %%<\/p>\n<p>6.\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 main()<\/p>\n<p>7.\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 {\u00a0 yylex();<\/p>\n<p>8.\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 printf( &#8220;# of lines = %d\\n&#8221;, num_lines); }<\/p>\n<p>&nbsp;<\/p>\n<p><strong>Example 8.1 LEX program to count the number of lines<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">Line 1 of this program belongs to the declaration section and declares an integer variable num_lines and initializes it to 0 and this concludes the first section. In the translation rules section the pattern in \u2015\\n\u2016 which is defined in line 3 needs to be matched with the action, incrementing the variable num_lines. This statement indicates whenever a new line is encountered which is defined by \\n, the line number is incremented. The third section is from line numbers 6 to 8. yylex( ) points to the text defined in the input stream and as long as data exists in the input, the line numbers are counted and printed in Line 8.<\/p>\n<\/div>\n<div>\n<p>&nbsp;<\/p>\n<p>Example 8.2 is an extension of example 8.1 where number of characters, words and lines are counted.<\/p>\n<p>&nbsp;<\/p>\n<p>1.\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 %{ int nchar, nword, nline; %}<\/p>\n<p>2.\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 %%<\/p>\n<p>3.\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 \\n { nline++; nchar++; }<\/p>\n<p>4.\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 [^ \\t\\n]+ { nword++, nchar += yyleng; } . { nchar++; }<\/p>\n<p>5.\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 %%<\/p>\n<p>6.\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 int main(void)<\/p>\n<p>7.\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 { yylex();<\/p>\n<p>8.\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 printf(&#8220;%d\\t%d\\t%d\\n&#8221;, nchar, nword, nline);<\/p>\n<p>9.\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 return 0; }<\/p>\n<p>&nbsp;<\/p>\n<p><strong>Example 8.2 LEX program to count number of lines, characters and words<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">In this example \u2015\\n\u2016 is mapped to increment the number of characters and number of lines, while \\t, a tab space is used to increment the number of words and number of characters which is defined in line numbers 3 and 4. Lines 6 to 9 represent the main function, which uses yylex to point to the text and processes it to count the number of lines, characters and words.<\/p>\n<p>&nbsp;<\/p>\n<p>Table 8.2 is a summary of some of the yy() commands that can be used in LEX program.<\/p>\n<p>&nbsp;<\/p>\n<table class=\"aligncenter\">\n<tbody>\n<tr>\n<td style=\"width: 202.063px\"><\/td>\n<td style=\"width: 442.063px\"><strong>Table 8.2<\/strong><\/td>\n<\/tr>\n<tr>\n<td style=\"width: 202.063px\"><\/td>\n<td style=\"width: 442.063px\"><\/td>\n<\/tr>\n<tr>\n<td style=\"width: 202.063px\"><strong>Name<\/strong><\/td>\n<td style=\"width: 442.063px\"><strong>Function<\/strong><\/td>\n<\/tr>\n<tr>\n<td style=\"width: 202.063px\">int yylex(void)<\/td>\n<td style=\"width: 442.063px\">call to invoke lexer, returns token<\/td>\n<\/tr>\n<tr>\n<td style=\"width: 202.063px\">char *yytext<\/td>\n<td style=\"width: 442.063px\">pointer to matched string<\/td>\n<\/tr>\n<tr>\n<td style=\"width: 202.063px\">yyleng<\/td>\n<td style=\"width: 442.063px\">length of matched string<\/td>\n<\/tr>\n<tr>\n<td style=\"width: 202.063px\">yylval<\/td>\n<td style=\"width: 442.063px\">value associated with token<\/td>\n<\/tr>\n<tr>\n<td style=\"width: 202.063px\">int yywrap(void)<\/td>\n<td style=\"width: 442.063px\">wrapup, return 1 if done, 0 if not done<\/td>\n<\/tr>\n<tr>\n<td style=\"width: 202.063px\">FILE *yyout<\/td>\n<td style=\"width: 442.063px\">output file<\/td>\n<\/tr>\n<tr>\n<td style=\"width: 202.063px\">FILE *yyin<\/td>\n<td style=\"width: 442.063px\">input file<\/td>\n<\/tr>\n<tr>\n<td style=\"width: 202.063px\">INITIAL<\/td>\n<td style=\"width: 442.063px\">initial start condition<\/td>\n<\/tr>\n<tr>\n<td style=\"width: 202.063px\">BEGIN condition<\/td>\n<td style=\"width: 442.063px\">switch start condition<\/td>\n<\/tr>\n<tr>\n<td style=\"width: 202.063px\">ECHO<\/td>\n<td style=\"width: 442.063px\">write matched string<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<p>The syntax and compilation procedure of FLEX program is the same as that of the LEX program.<\/p>\n<\/div>\n<div>\n<p><strong>8.4 JLEX program<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">A typical JLEX program also consists of three parts. In the case of JLEX program, the organization is slightly different. The first section represents the user code which is later copied directly as a Java file. The second section consists of JLEX directives, where macros and other state names are typically defined. Here again, \u2015%%\u2016 is used as a delimiter to separate one section from the other. The third section consists of the translation rules that define regular expressions along with the necessary actions. The user code is copied to a java file and a JAVA compiler is used instead of a C compiler of the LEX program to compile and execute the JLEX program. The following is a simple layout of a JLEX file.<\/p>\n<p>&nbsp;<\/p>\n<p>User code<\/p>\n<p><strong>%%<\/strong><\/p>\n<p>JLex directives<\/p>\n<p><strong>%%<\/strong><\/p>\n<p>Lexical analysis rules<\/p>\n<p>&nbsp;<\/p>\n<p>Example 8.3 is a JLEX program to count the number of lines in an input document.<\/p>\n<p>&nbsp;<\/p>\n<p>1.\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 import java_cup.runtime.*;<\/p>\n<p>2.\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 %%<\/p>\n<p>3.\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 %cup<\/p>\n<p>4.\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 %{<\/p>\n<p>5.\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 private int lineCounter = 0;<\/p>\n<p>6.\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 %}<\/p>\n<p>7.\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 %eofval{<\/p>\n<p>8.\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 System.out.println(&#8220;line number=&#8221; + lineCounter);<\/p>\n<p>9.\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 return new Symbol(sym.EOF);<\/p>\n<p>10.\u00a0\u00a0 %eofval}<\/p>\n<p>11.\u00a0\u00a0 NEWLINE=\\n<\/p>\n<p>12.\u00a0\u00a0 %%<\/p>\n<p>13.\u00a0\u00a0 {NEWLINE} {<\/p>\n<p>14.\u00a0\u00a0 lineCounter++;<\/p>\n<p>15.\u00a0\u00a0 }<\/p>\n<p>16.\u00a0\u00a0 [^{NEWLINE}] { }<\/p>\n<p>&nbsp;<\/p>\n<p><strong>Example8.3 Sample JLEX program<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">In example 8.3, line number 1 indicates the user code which gets copied to the java file. %cup is used to activate the Java CUP compatibility that helps conform to the java_cup.runtime and<\/p>\n<\/div>\n<p style=\"text-align: justify\">initiates the scanner. The Java CUP compatibility is turned off by default and hence every JLEX program needs to get activate as the first step. %eofval is used to indicate \u2015end of value\u2016 of the input. The variable line number is incremented for every NEWLINE encountered in line number<\/p>\n<ol start=\"14\">\n<li style=\"text-align: justify\">NEWLINE is a name given to the \u2015\\n\u2016 character which indicates the encounter of a new line. This is again a rule based programming language and hence does not obey the flow of a structured programming language.<\/li>\n<\/ol>\n<p>&nbsp;<\/p>\n<p><strong>Summary<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">This module discussed the use of tools LEX and JLEX for tokenizing the input. Designing and implementing the lexical phase of the compiler is difficult and hence tools can be used to do the job of tokenizing using a rule based programming language. The tools use regular expressions to define the pattern and a corresponding action. When the regular expression matches a pattern, the defined action is used to perform a task.<\/p>\n<\/li>\n<\/ul>\n","protected":false},"author":4,"menu_order":8,"template":"","meta":{"pb_show_title":"on","pb_short_title":"","pb_subtitle":"","pb_authors":["dr-rajeswari-sridhar"],"pb_section_license":""},"chapter-type":[],"contributor":[59],"license":[],"class_list":["post-145","chapter","type-chapter","status-publish","hentry","contributor-dr-rajeswari-sridhar"],"part":3,"_links":{"self":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-json\/pressbooks\/v2\/chapters\/145","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-json\/pressbooks\/v2\/chapters"}],"about":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-json\/wp\/v2\/types\/chapter"}],"author":[{"embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-json\/wp\/v2\/users\/4"}],"version-history":[{"count":2,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-json\/pressbooks\/v2\/chapters\/145\/revisions"}],"predecessor-version":[{"id":148,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-json\/pressbooks\/v2\/chapters\/145\/revisions\/148"}],"part":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-json\/pressbooks\/v2\/parts\/3"}],"metadata":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-json\/pressbooks\/v2\/chapters\/145\/metadata\/"}],"wp:attachment":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-json\/wp\/v2\/media?parent=145"}],"wp:term":[{"taxonomy":"chapter-type","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-json\/pressbooks\/v2\/chapter-type?post=145"},{"taxonomy":"contributor","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-json\/wp\/v2\/contributor?post=145"},{"taxonomy":"license","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-json\/wp\/v2\/license?post=145"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}