Build an interpreter and a compiler to C ++ for the language BOOLexp using flex and bison

chaper10.pdf

Home >Computer Science homework help >Build an interpreter and a compiler to C ++ for the language BOOLexp using flex and bison

C O

N F ID

E N

T IA

L D

R A

F T

Chapter 10

Automatic Program Generation

10.1 Chapter Objectives

• Establish an understanding of flex and bison.

• Differientiate between . . . .

• Introduce . . . .

10.2 Scanner Generation: flex

10.2.1 Outline

10.2.2 Linux Tools for Automatically Generating Scanners and Parsers

flex and bison are the GNU versions of lex and yacc (yet another com- piler compiler), respectively.

10.2.3 Structure of a flex Specification:

277

C O

N F ID

E N

T IA

L D

R A

F T278 CHAPTER 10. AUTOMATIC PROGRAM GENERATION

Listing 10.2: Our first flex program: cat (version 0).

2 %% 3

4 %% 5

6 /* c a l l e d by f l e x when EOF r e a c h e d */ 7 i n t yywrap ( void ) { 8 /* c o n v e n t i o n i s t o r e t u r n 1 */ 9 r e t u r n 1 ;

10 } 11

12 i n t main ( void ) { 13 /* main e n t r y p o i n t f o r f l e x */ 14 yylex ( ) ; 15 r e t u r n 0 ; 16 }

Listing 10.1: Structure of a flex specification.

1 /* d e f i n i t i o n s */ 2

3 %% 4

5 /* a s e t o f p a t t e r n−a c t i o n r u l e s */ 6

7 %% 8

9 /* s u b r o u t i n e s */

10.2.4 Our First flex Program: cat (version 0)

10.2.5 noop

10.2.6 cat (version 1)

10.2.7 Running flex to Automatically Generate a Scanner

1 $ flex c a t . l # p r o d u ce s l e x . yy . c 2 $ gcc lex . yy . c # p r o d u ce s a . out , t h e e x e c u t a b l e f o r t h e s c a n n e r 3 $ . /a . out # r u n s t h e s c a n n e r

C O

N F ID

E N

T IA

L D

R A

F T10.2. SCANNER GENERATION: FLEX 279

Listing 10.3: Noop: noop.l.

1 /* noop . l */ 2

3 %% 4

5 . { } 6 \n { } 7

8 %% 9

10 i n t yywrap ( ) { 11 r e t u r n 1 ; 12 } 13

14 i n t main ( ) { 15 yylex ( ) ; 16 r e t u r n 0 ; 17 }

Listing 10.4: cat version 1.

1 /* c a t 1 . l */ 2

3 %% 4

5 . /* match any c h a r a c t e r e x c e p t n e w l i n e */ printf ( "%s" , yytext) ; 6

7 \n /* match n e w l i n e */ printf ( "\n") ; 8

9 %% 10

11 i n t yywrap ( void ) { 12 r e t u r n 1 ; 13 } 14

15 i n t main ( void ) { 16 yylex ( ) ; 17 r e t u r n 0 ; 18 }

C O

N F ID

E N

T IA

L D

R A

F T280 CHAPTER 10. AUTOMATIC PROGRAM GENERATION

Listing 10.5: cat version 2.

1 /* c a t 2 . l */ 2

3 %% 4

5 . ECHO ; 6

7 \n ECHO ; 8

9 %% 10

11 i n t yywrap ( void ) { 12 r e t u r n 1 ; 13 } 14

15 i n t main ( i n t argc , c h a r * * argv) { 16 printf ( ":%s:\n" , argv [ 1 ] ) ; 17 i f ( ( yyin = fopen ( argv [ 1 ] , "r" ) ) == NULL) 18 printf ( "broken\n") ; 19 i f ( yyin == stdin) 20 printf ( "here\n" ) ; 21 e l s e

22 printf ( "there\n" ) ; 23

24 yylex ( ) ; 25 fclose ( yyin) ; 26 r e t u r n 0 ; 27 }

. . . or use a Makefile (more on this later) 10.2.8 cat (version 2)

10.2.9 cat (version 3)

10.2.10 cat -n (version 4)

10.2.11 cat -n (version 5)

10.2.12 Word Count

10.2.13 Pattern Overlap

10.2.14 Identifying Identifiers

10.2.15 Matching Quoted Strings

10.2.16 States

• %s ONE creates the (regular) start state ONE

C O

N F ID

E N

T IA

L D

R A

F T10.2. SCANNER GENERATION: FLEX 281

Listing 10.6: cat version 3.

1 /* c a t 3 . l */ 2

3 %{ 4 i n t cc= 0 ; 5 %} 6

7 %% 8

9 . { cc+ + ; ECHO ; } 10

11 \n { cc+ + ; ECHO ; } 12

13 %% 14

15 i n t yywrap ( void ) { 16 r e t u r n 1 ; 17 } 18

19 i n t main ( i n t argc , c h a r * * argv) { 20 yyin = fopen ( argv [ 1 ] , "r" ) ; 21 yylex ( ) ; 22 fclose ( yyin) ; 23 printf ( "%d characters\n" , cc ) ; 24 r e t u r n 0 ; 25 }

C O

N F ID

E N

T IA

L D

R A

F T282 CHAPTER 10. AUTOMATIC PROGRAM GENERATION

Listing 10.7: cat -n version 4.

1 /* c a t 4 . l ( c a t −n ) */ 2

3 %{ 4 i n t cc = 0 ; 5 i n t lineno = 0 ; 6 %} 7

8 %% 9

10 ^ . * \n { cc += strlen( yytext) ; 11 printf ( "%d %s" , ++lineno , yytext) ; } 12 %% 13

14 i n t yywrap ( ) { 15 r e t u r n 1 ; 16 } 17

18 i n t main( i n t argc , c h a r * * argv) { 19 yyin = fopen ( argv [ 1 ] , "r" ) ; 20 yylex ( ) ; 21 printf ( "%d characters.\n" , cc) ; 22 fclose( yyin) ; 23 r e t u r n 0 ; 24 }

C O

N F ID

E N

T IA

L D

R A

F T10.2. SCANNER GENERATION: FLEX 283

Listing 10.8: cat -n version 5.

1 /* c a t 5 . l ( c a t −n ) */ 2

3 %option yylineno 4

5 %{ 6 i n t cc = 0 ; 7 %} 8

9 %% 10 ^ . * \n { cc += strlen( yytext) ; 11 printf( "%4d\t%s" , yylineno−1 , yytext) ; } 12

13 %% 14

15 i n t yywrap ( void ) { 16 r e t u r n 1 ; 17 } 18

19 i n t main ( i n t argc , c h a r * * argv) { 20 yyin = fopen ( argv [ 1 ] , "r" ) ; 21 yylex ( ) ; 22 printf ( "%d characters.\n" , cc) ; 23 fclose ( yyin) ; 24 r e t u r n 0 ; 25 }

C O

N F ID

E N

T IA

L D

R A

F T284 CHAPTER 10. AUTOMATIC PROGRAM GENERATION

Listing 10.9: Word count (wc).

1 %{ 2 i n t cc = 0 ; 3 i n t wc = 0 ; 4 i n t lc = 0 ; 5 %} 6

8 %% 9

10 \n { lc+ + ; cc+ + ; } 11

12 [ \t] { cc+ + ; } 13

14 [ ^ \t\n] + { wc+ + ; cc += yyleng ; /* c o u n t a n y t h i n g bu t w h i t e s p a c e */ } 15

16 %% 17

18 i n t yywrap ( ) { 19 r e t u r n 1 ; 20 } 21

22 i n t main( i n t argc , c h a r * * argv) { 23 yyin = fopen ( argv [ 1 ] , "r" ) ; 24 yylex ( ) ; 25 printf ( "%8d%8d%8d\n" , lc , wc , cc) ; 26 fclose( yyin) ; 27 r e t u r n 0 ; 28 }

C O

N F ID

E N

T IA

L D

R A

F T10.2. SCANNER GENERATION: FLEX 285

Listing 10.10: Pattern overlap in word count (wc2.l).

1 %{ 2 i n t cc = 0 ; 3 i n t wc = 0 ; 4 i n t lc = 0 ; 5 %} 6

8 %% 9

10 [ ] { printf( "Found a space.\n") ; } 11

12 [ \t] { cc+ + ; } 13

14 \n { lc+ + ; cc+ + ; } 15

16 [ ^ \t\n] + { wc+ + ; cc += yyleng ; /* c o u n t a n y t h i n g bu t w h i t e s p a c e */ } 17

18 %% 19

20 i n t yywrap ( ) { 21 r e t u r n 1 ; 22 } 23

24 i n t main( i n t argc , c h a r * * argv) { 25 yyin = fopen ( argv [ 1 ] , "r" ) ; 26 yylex ( ) ; 27 printf ( "%8d%8d%8d\n" , lc , wc , cc) ; 28 fclose( yyin) ; 29 r e t u r n 0 ; 30 }

C O

N F ID

E N

T IA

L D

R A

F T286 CHAPTER 10. AUTOMATIC PROGRAM GENERATION

Listing 10.11: Identifying identifiers (idcount.l).

1 %{ 2 i n t idcount= 0 ; 3 %} 4

5 alpha [ _a−zA−Z ] 6 alphanumeric [ _a−zA−Z0−9] 7 digit [0−9] 8

10 %% 11

12 { alpha } { alphanumeric} * { idcount+ + ; printf( "%s\n" , yytext) ; } 13 { alpha } ( { alpha} | { digit } ) * { idcount+ + ; ECHO ; printf( "\n" ) ; } 14

15 . { } 16 \n { } 17

18 %% 19

20 i n t yywrap ( void ) { 21 r e t u r n 1 ; 22 } 23

24 i n t main ( i n t argc , c h a r * * argv) { 25 yyin = fopen ( argv [ 1 ] , "r" ) ; 26 yylex ( ) ; 27 fclose( yyin) ; 28 printf ( "This program contains %d identifiers.\n" , idcount) ; 29 r e t u r n 0 ; 30 }

C O

N F ID

E N

T IA

L D

R A

F T10.2. SCANNER GENERATION: FLEX 287

Listing 10.12: Matching quoted strings (quotedStrings.l).

1 %{ 2 # i n c l u d e < s t r i n g . h> 3 e x t e r n i n t yy_flex_debug; 4 c h a r * yylval = NULL ; 5 %} 6

7 %% 8

9 [ "][^"\n ] * [ "] { printf (":%s: \n", yytext); 10 yylval = strdup(yytext+1);

11 /* yylval[strlen(yylval)-1] = '\0'; */

12 yylval[yyleng-2] = '\0';

13 printf (":%s: \n", yylval); } 14

15 ["] [ ^ "\n]*[\n] { fprintf (stderr, ":%s: \n", yytext); 16 warning("Invalid string : "); 17 printf (":%s: \n", yytext+1); } 18

19 \n { }

20 . { }

22 %%

24 int yywrap() {

25 return 1;

26 }

28 int warning (char* s) {

29 fprintf (stderr, "%s\n", s); 30 return 2;

31 }

33 int main(int argc, char** argv) {

34 /* flex -d to enable debugging statements */

35 yy_flex_debug = 1;

36 yylex();

37 return 0;

38 }

C O

N F ID

E N

T IA

L D

R A

F T288 CHAPTER 10. AUTOMATIC PROGRAM GENERATION

all

a.out

lex.yy.c

Cstrings.l

Figure 10.1: Makefile dependency graph for C strings.

Table 10.1: Pattern matching primitives. Metacharacter Matches . any character except newline \n newline

* zero or more copies of the preceding expression + one or more copies of the preceding expression ? zero or one copy of the preceding expression ˆ beginning of line $ end of line a | b a or b (ab)+ one or more copies of ab (grouping) “a+b” literal “a+b” (C escapes still work) [] character class

• ‘rules that do not have start states can apply in any state’ [Nie, p. 172]

• %x TWO creates the exclusive start state TWO

• ‘a rule with no start state is not matched when an exclusive state is active’ [Nie, p. 172]

10.2.17 Matching C Strings

10.2.18 Conceptual Exercises for Section 10.2

Exercise 10.2.1: Define a regular expression to match a string containing balanced parentheses (e.g., ((())()) is balanced, (()() is unbalanced) not state why it is not possible.

C O

N F ID

E N

T IA

L D

R A

F T10.2. SCANNER GENERATION: FLEX 289

Listing 10.13: States (states.l).

1 %{ 2 %} 3

4 %x ONE 5 %x TWO 6

8 %% 9

10 a { BEGIN ONE ; printf( "in ZERO; read a; goto ONE\n") ; } 11

12 b { BEGIN TWO ; printf( "in ZERO; read b; goto TWO\n") ; } 13

14 <TWO>a { printf ( "in TWO; read a; goto 0\n") ; BEGIN 0 ; } 15 <TWO>b { printf ( "in TWO; read b; goto 0\n") ; BEGIN 0 ; } 16 <ONE>a { printf ( "in ONE; read a; goto TWO\n" ) ; BEGIN TWO ; } 17 <ONE>b { printf ( "in ONE; read b; goto TWO\n" ) ; BEGIN TWO ; } 18

19 . { } 20 \n { } 21 <ONE> . { } 22 <ONE>\n { } 23 <TWO> . { } 24 <TWO>\n { } 25

26 %% 27

28 i n t yywrap ( ) { 29 r e t u r n 1 ; 30 } 31

32 i n t main ( ) { 33 yylex ( ) ; 34 r e t u r n 0 ; 35 }

C O

N F ID

E N

T IA

L D

R A

F T290 CHAPTER 10. AUTOMATIC PROGRAM GENERATION

Listing 10.14: Matching C strings (Cstrings.l).

1 %{ 2 e x t e r n i n t yy_flex_debug; 3 c h a r buf [ 1 0 0 ] ; 4 c h a r * s = NULL ; 5

6 %} 7

8 %x INQUOTE 9

10 %% 11

12 \" { BEGIN INQUOTE; s = buf; } 13

14 <INQUOTE>\\\" { *s++ = '\"'; fprintf(stderr, "found escaped quote\n"←֓ ); }

15 <INQUOTE>\\\n { fprintf(stderr, "found escaped newline\n"); } 16 <INQUOTE>\\n { *s++ = '\n'; fprintf(stderr, "found newline\n"); } 17 <INQUOTE>\\t { *s++ = '\t'; fprintf(stderr, "found tab\n"); } 18

19 <INQUOTE>[" ] { *s = '\0' ; 20 BEGIN 0 ; 21 printf ( "\nFound :%s:\n" , buf) ; } 22

23 <INQUOTE>\n { BEGIN 0 ; fprintf ( stderr , "Invalid string.\n" ) ; /* ←֓ e x i t ( 1 ) ; */ }

26 <INQUOTE> . { *s++ = *yytext ; } 27

28 \n { } 29 . { } 30

31 %% 32

33 i n t yywrap ( ) { 34 r e t u r n 1 ; 35 } 36

37 i n t main ( ) { 38 yy_flex_debug = 0 ; 39 yylex ( ) ; 40 r e t u r n 0 ; 41 }

C O

N F ID

E N

T IA

L D

R A

F T10.2. SCANNER GENERATION: FLEX 291

Listing 10.15: Makefile for C strings (Makefile).

1 SRC = Cstrings . l 2 CC = gcc 3 LEX = flex 4 LEX_FLAGS = −d 5 OBJ = lexer 6

7 all : $( OBJ) 8

9 $ ( OBJ) : lex . yy . c 10 $ ( CC) −o $ ( OBJ) lex . yy . c 11

12 lex . yy . c : $ ( SRC) 13 $ ( LEX) $ ( LEX_FLAGS) $ ( SRC) 14

15 clean : 16 @−rm lex . yy . c $( OBJ)

Table 10.2: Pattern matching examples. Expression Matches

abc abc abc* ab, abc, abcc, abccc, . . . abc+ abc, abcc, abccc, abcccc, . . . a(bc)+ abc, abcbc, abcbcbc, ... a(bc)? a, abc [abc] one of: a, b, c [a-z] any letter, a through z [a\-z] one of: a, -, z [-az] one of: -, a, z [A-Za-z0-9]+ one or more alphanumeric characters [ \t\n]+ whitespace [ˆab] anything except: a, b [aˆb] a, ˆ, b [a | b] a, |, b a | b a, b

C O

N F ID

E N

T IA

L D

R A

F T292 CHAPTER 10. AUTOMATIC PROGRAM GENERATION

Table 10.3: flex predefined variables. Name Function

int yylex(void) call to invoke lexer, returns token char* yytext pointer to matched string yyleng length of matched string yylval value associated with token int yywrap(void) wrapup, return 1 if done, 0 if not done FILE* yyout output file FILE* yyin input file INITIAL initial start condition BEGIN condition switch start condition ECHO write matched string

10.2.19 Programming Exercises for Section 10.2

Exercise 10.2.2: Define a flex specification for a program that writes to stdout each line of its standard input with all leading and trailing whites- pace purged from every line.

Exercise 10.2.3: Define a flex specification for a program that writes to stdout each line of its standard input with all leading and trailing whites- pace purged from every line, and all blank lines purged.

Exercise 10.2.4: Define a flex specification for the Linux wc command. You need not handle file I/O or command-line options (assume -l, -w, and -c are always present).

Exercise 10.2.5: Define a flex specification for the Linux wc command. The scanner generated must support both standard input and file input. You need not handle command-line options (assume -l, -w, and -c are always present).

Exercise 10.2.6: Consider the input stream given in Exercise 8.3.. Define a flex specification for a program to convert each line of standard input in the form (<last>,<first>) to (<first> 2 <first>) and print the results to stdout, where 2 represents a single space character.

Exercise 10.2.7: Consider the input stream given in Programming Ex- ercise 8.3.. Define a flex specification for a program to con- vert each line of standard input in the form (<last>,<first>) to

C O

N F ID

E N

T IA

L D

R A

F T10.2. SCANNER GENERATION: FLEX 293

(<first> 2 <first>) and print the results, with any leading and trail- ing whitespace, and all blank lines, purged, to standard output, where 2 represents a single space character.

Exercise 10.2.8: Rewrite the flex specification for matching quoted strings in Listing 10.12 by combining the two pattern-action rules into one pattern-action rule.

10.2.20 Programming Projects for Section 10.2

Exercise 10.2.1: Automatically generate a lexical analyzer which outputs the uncommented and commented included header filenames from a stream of C/C++ source code.

Requirements:

a) Your program must read from standard input and file input, but always write to standard output.

b) Your program must support only two command-line options (-u and -c) and combinations of them (e.g., -uc and -cu).

c) When run with no command-line options, your program must print both uncommented and commented included header filenames (and nothing else) using the format used in the sample output given below.

d) When run with the -u command-line option, your program must print only the uncommented included header filenames (and nothing else) us- ing the format used in the sample output given below.

e) When run with the -c command-line option, your program must print only the commented included header filenames (and nothing else) using the format used in the sample output given below.

f) When run with the -u and -c command-line options or the -uc or -cu command-line options, your program must print both the uncommented and commented included header filenames (and nothing else) using the format used in the sample output given below.

g) If an invalid option <option> is given, the program must print ./showheaders: Illegal option: <option> and a usage mes- sage to stderr and halt with a exit status 1 as shown below.

C O

N F ID

E N

T IA

L D

R A

F T294 CHAPTER 10. AUTOMATIC PROGRAM GENERATION

1 $ . /showheaders −t 2 . /showheaders : Illegal option −t 3 Usage : showheaders [−cu] [ file( s ) . . . ] 4 $ echo $? 5 1

h) If an invalid file <file> is given, the program must print ./showheaders: Invalid file: <file> and a usage message to stderr and and halt with exit status 2.

1 $ . /showheaders somefile 2 . /showheaders : Invalid file : somefile 3 Usage : showheaders [−cu] [ file( s ) . . . ] 4 $ echo $? 5 2

i) You may assume that the input stream will never contain more than fifty (uncommented or commented) included header filenames.

j) You may assume that if you encounter an opening /* comment token that the closing */ comment token will always be on the same line. More generally, you may assume that the input stream will be syntactically valid C/C++ source code.

k) Note that comments may contain both text and an include file:

1 /* T h i s i s my comment abo u t # i n c l u d e < s t d i o . h> */ 2

3 // T h i s i s my comment abo u t # i n c l u d e < s t d i o . h>

l) Your solution must contain only a flex specification file and a Makefile (i.e., no other source files).

m) Use macros and substitutions (e.g., digit [0-9]), where possible and appropriate, to simply the pattern-matching rules in your flex specifi- cation file.

n) Develop a Makefile which builds your lexical analyzer. Your Makefile must include target directives for every derived file produced during the compilation process (i.e., each program, each object file, and any other intermediate files produced during code generation and com- pilation). Make sure that each directive also lists all files on which the derived file depends in its dependency list. Also, your Makefile must

C O

N F ID

E N

T IA

L D

R A

F T10.3. PARSER GENERATION: BISON 295

yes / nosource program (regular grammar) list of

tokens

(context−free grammar) parserscanner(string or

list of lexemes)

Figure 10.2: Simplified view of scanning and parsing: the front end.

be written so carries out only the commands necessary to bring any pro- duced file up-to-date. Your Makefile must do just enough, but no ex- tra, work to bring showheaders (the final executable for your lexical analyzer) up-to-date every time make is invoked. In addition, it must have an all directive and a clean directive to remove all generated files. Use variables where appropriate in your Makefile to improve its readability. Your Makefile must bring everything up-to-date, us- ing only lex and gcc, without any warnings or errors, when make is invoked.

Sample test data is available at http://perugini.cps.udayton.edu/ teaching/books/SPUC/www/files/showheadersdata.tar, and a sample test session with showheaders on that data is available at http://perugini.cps.udayton.edu/teaching/books/SPUC/ www/files/showheaderstestsession.txt.

Exercise 10.2.2: Complete Programming Project 10.2.1 in Go, subject to all the requirements given in that specification. Use the Nex (nex) lexical analyzer generator for Go available at: https://crypto.stanford. edu/~blynn/nex/.

10.3 Parser Generation: bison

10.3.1 Scanning and Parsing

10.3.2 Evaluating Arithmetic Expressions in Linux

1 $ expr 2 + 3 2 5 3 $ expr 2 + 3 \* 4 4 14 5 $ expr 2 \* 3 + 4 6 10

http://perugini.cps.udayton.edu/teaching/books/SPUC/www/files/showheadersdata.tar

http://perugini.cps.udayton.edu/teaching/books/SPUC/www/files/showheaderstestsession.txt

https://crypto.stanford.edu/~blynn/nex/

C O

N F ID

E N

T IA

L D

R A

F T296 CHAPTER 10. AUTOMATIC PROGRAM GENERATION

yes / no

yacclex

source program list of

tokens(string or list of lexemes)

.yregular grammar ( ).l context−free grammar ( )

lex.yy.c

scanner parser .tab.h .tab.c

Figure 10.3: Simplified view of scanning and parsing: the front end with flex and bison.

yes / no

id1 = id2 * id3 + id4

scanner

parser

list of tokens

"n = x * y + z"source program (string)

Figure 10.4: More detailed view of scanning and parsing.

7 $ expr "2 + 3 * 4"

8 2 + 3 * 4

6 23+47

7 70

8 2 + 3

9 5

10 2 + 3 * 4

11 14

12 2 * 3 + 4

13 10

C O

N F ID

E N

T IA

L D

R A

F T10.3. PARSER GENERATION: BISON 297

.tab.c

lex regular grammar ( )

yacc context−free grammar ( )

id1 = id2 * id3 + id4

scanner

list of tokens

"n = x * y + z"source program (string)

yes / no =

lex.yy.c

parser .tab.h

Figure 10.5: More detailed view of scanning and parsing with flex and bison.

14 2 ^ 3

15 8

16 ^D

10.3.3 Calculator (version 1)

The following is a context-free grammar in ENBF defining a language of calculator expressions which we use as a running example in this chapter.

<program> ::= <program> <expr> \n | <expr> \n <expr> ::= (<list>) | a

<integer> ::= 1 | 2 | 3 | . . . |∞

Hack to deal with an ambiguous grammar. bison Conflicts

%left ’+’ ’-’

%left ’*’ ’/’

1 %token INTEGER

C O

N F ID

E N

T IA

L D

R A

F T298 CHAPTER 10. AUTOMATIC PROGRAM GENERATION

Listing 10.16: calc1.l.

1 %{ 2 # i n c l u d e "calc1.tab.h"

3 /* 4 # d e f i n e YYSTYPE i n t 5 e x t e r n YYSTYPE y y l v a l ; 6 */ 7 %} 8

9 %% 10

11 0 { 12 /* g e t i n t e g e r v a l u e o f INTEGER t o k e n */ 13 yylval = atoi ( yytext) ; 14 r e t u r n INTEGER ; 15 } 16

17 [ 1−9 ] [ 0−9 ] * { 18 /* g e t i n t e g e r v a l u e o f INTEGER t o k e n */ 19 yylval = atoi ( yytext) ; 20 r e t u r n INTEGER ; 21 } 22

23 [−+\n ] { r e t u r n *yytext ; } 24

25 [ \t] ; /* s k i p w h i t e s p a c e */ 26

27 . yyerror ( "invalid character" ) ; 28

29 %% 30

31 i n t yywrap ( void ) { 32 r e t u r n 1 ; 33 }

C O

N F ID

E N

T IA

L D

R A

F T10.3. PARSER GENERATION: BISON 299

Listing 10.17: calc1.y.

1 /* t o k e n v a l u e s t y p i c a l l y s t a r t around 258 2 b e c a u s e v a l u e s 0−255 a r e r e s e r v e d f o r c h a r a c t e r v a l u e s and 3 l e x r e s e r v e s s e v e r a l v a l u e s f o r end−o f−f i l e and e r r o r p r o c e s s i n g 4 */ 5

6 /* p r o d u ce s " # d e f i n e INTEGER 2 5 8 " i n y . t a b . c on our s y s t e m */ 7 %token INTEGER 8

9 %{ 10 # i n c l u d e < s t d i o . h> 11 # d e f i n e YYDEBUG 0 12 %} 13

14 %left '+' '-' 15

16 %% 17

18 program : program expr '\n' { printf ( "%d\n" , $2) ; } 19 | expr '\n' { printf ( "%d\n" , $1 ) ; } 20 ; 21

22 expr : INTEGER { $$ = $1 ; /* d e f a u l t a c t i o n : pop , push */ } 23

24 | expr '+' expr { 25 /* a d d i t i o n */ 26 $$ = $1 + $3 ; 27 } 28

29 | expr '-' expr { 30 /* s u b t r a c t i o n */ 31 $$ = $1 − $3 ; 32 } 33 ; 34

35 %% 36

37 i n t yyerror ( c h a r * s ) { 38 fprintf ( stderr , "%s\n" , s ) ; 39 r e t u r n 0 ; 40 } 41

42 i n t main ( void ) { 43 # i f YYDEBUG 44 yydebug = 0 ; 45 // y y _ f l e x _ d e b u g = 1 ; 46 # e n d i f

47 yyparse ( ) ; 48 r e t u r n 0 ; 49 }

C O

N F ID

E N

T IA

L D

R A

F T300 CHAPTER 10. AUTOMATIC PROGRAM GENERATION

value stack

contains terminals

represents current parsing state

and non−terminals; an array of YYSTYPE elements

$$ = top of stack

<expr>

’+’

<expr>

’+’

tokens yylvals

<expr> $$ 54

parse stack

Figure 10.6: Parse stack and value stacks in bison.

inptut (e.g., source code) gram.y

lex.yy.c

(contains

tokens.l

(contains

gcc

s#include

gram.tab.c

gram.tab.h

output (e.g., parse tree)

(defines )

of grammar) (EBNF specification

YYSTYPE

)yylex()

yyparse() )

(regular expression specification of

tokens)

bison

flex

a.out

Figure 10.7: Marriage of flex and bison.

2 /* p r o d u ce s " # d e f i n e INTEGER 2 5 8 " i n c a l c . t a b . c 3 b e c a u s e v a l u e s 0−255 a r e r e s e r v e d f o r c h a r a c t e r v a l u e s , and 4 l e x r e s e r v e s s e v e r a l v a l u e s f o r end−o f−f i l e and e r r o r p r o c e s s i n g 5 and , t h e r e f o r e , t o k e n v a l u e s t y p i c a l l y s t a r t around 258 */

10.3.4 Marriage of flex and bison

10.3.5 Running bison (in conjunction with flex) to Generate a Parser

[Nie][p. 5]

[Nie][p. 5] Fig. 10.7 illustrates how flex and bison collaborate to generate a

parser.

1 $ flex tokens . l # p r o d u ce s l e x . yy . c

C O

N F ID

E N

T IA

L D

R A

F T10.3. PARSER GENERATION: BISON 301

inptut (e.g., source code)

lex.yy.c

(contains

gcc

s#include

output (e.g., parse tree)

(defines )

of grammar) (EBNF specification

YYSTYPE

)yylex()

yyparse() )

(regular expression specification of

tokens)

bison

flex

a.out

calc1.y

calc1.l

calc1.tab.c

calc1.tab.h

Figure 10.8: Marriage of flex and bison in calculator.

2 $ bison −d gram . y # p r o d u ce s gram . t a b . c and gram . t a b . h 3 $ gcc −c gram . tab . c # p r o d u ce s gram . t a b . o 4 $ gcc −c lex . yy . c # p r o d u ce s l e x . yy . o 5 $ gcc −o parser gram . tab . o lex . yy . o # p r o d u ce s p a r s e r 6 $ . /parser < . . .

1 $ flex calc1 . l # p r o d u ce s l e x . yy . c 2 $ bison −d calc1 . y # p r o d u ce s c a l c 1 . t a b . c and c a l c 1 . t a b . h 3 $ gcc −c calc1 . tab . c # p r o d u ce s c a l c 1 . t a b . o 4 $ gcc −c lex . yy . c # p r o d u ce s l e x . yy . o 5 $ gcc −o parser calc1 . tab . o lex . yy . o # p r o d u ce s p a r s e r 6 $ . /calc1 < . . .

10.3.6 Calculator (version 2)

We extend the calculator of the previous section to incorporate the follow- ing new features:

• multiplication (*) and division (/) arithmetic operators,

• a unary minus operator (−),

• a exponentiation operator (ˆ) for non-negative exponents,

• parentheses to override operator precedence,

• single-character variables, and

• a print statement.

C O

N F ID

E N

T IA

L D

R A

F T302 CHAPTER 10. AUTOMATIC PROGRAM GENERATION

Listing 10.18: Makefile for calculator (version 1).

1 SRC = calc1 2 CC = gcc 3 LEX = flex 4 #LEX_FLAGS = −d 5 LEX_FLAGS = 6 YACC = bison 7 YACC_FLAGS = −d −t 8

9 all : $( SRC) 10

11 $ ( SRC) : lex . yy . o $ ( SRC) . tab . o 12 $ ( CC) lex . yy . o $ ( SRC) . tab . o −o $ ( SRC) 13

14 lex . yy . o : lex . yy . c $ ( SRC) . tab . h 15 $ ( CC) −c lex . yy . c 16

17 lex . yy . c : $ ( SRC) . l 18 $ ( LEX) $ ( LEX_FLAGS) $ ( SRC) . l 19

20 $ ( SRC) . tab . o : $( SRC) . tab . c 21 $ ( CC) −c $ ( SRC) . tab . c 22

23 $ ( SRC) . tab . c : $( SRC) . y 24 $ ( YACC) $ ( YACC_FLAGS) $ ( SRC) . y 25

26 $ ( SRC) . tab . h : $( SRC) . y 27 $ ( YACC) $ ( YACC_FLAGS) $ ( SRC) . y 28

29 clean : 30 −rm * . [ cho] $( SRC)

C O

N F ID

E N

T IA

L D

R A

F T10.3. PARSER GENERATION: BISON 303

Listing 10.19: calc2.l.

1 %{ 2 # i n c l u d e "calc2.tab.h"

3 %} 4

5 %% 6

7 [ a−z] { /* t h e p o s i t i o n o f t h e c h a r a c t e r i n t h e a l p h a b e t 0 . . 2 5 */ 8 yylval = *yytext − 'a' ; 9 r e t u r n VARIABLE ; }

11 0 { yylval = atoi ( yytext) ; 12 r e t u r n INTEGER ; } 13

14 [ 1−9 ] [ 0−9 ] * { yylval = atoi ( yytext) ; 15 r e t u r n INTEGER ; } 16

17 [−+ ( ) = */ ^ ; \n ] { /* o p e r a t o r s */ r e t u r n *yytext ; } 18

19 print { /* o p e r a t o r */ r e t u r n PRINT ; } 20

21 [ \t] { /* s k i p w h i t e s p a c e */ } 22

23 . { /* a n y t h i n g e l s e i s an e r r o r */ yyerror ( "invalid character" ) ; } 24

25 %% 26

27 i n t yywrap ( void ) { 28 r e t u r n 1 ; 29 }

C O

N F ID

E N

T IA

L D

R A

F T304 CHAPTER 10. AUTOMATIC PROGRAM GENERATION

Listing 10.20: calc2.y. 1 %token INTEGER VARIABLE PRINT 2 %right '=' 3 %left '+' '-' 4 %left '*' '/' 5 %right '^' 6 7 %{ 8 # i n c l u d e < s t d i o . h> 9 # i n c l u d e <math . h>

10 # d e f i n e SIZE 26 11 # d e f i n e YYDEBUG 0 12 i n t symtab[ SIZE ] ; 13 %} 14 15 %% 16 17 program : program statement ';' '\n' 18 | statement ';' '\n' 19 ; 20 21 statement : 22 expr 23 | PRINT expr { printf ( "%d\n" , $2 ) ; } 24 | VARIABLE '=' expr { symtab[ $1 ] = $3 ; } 25 ; 26 27 expr : 28 INTEGER 29 | VARIABLE { $$ = symtab[ $1 ] ; } 30 | '-' expr %prec '^' { $$ = $2* −1; } 31 | expr '*' expr { $$ = $1 * $3 ; } 32 | expr '/' expr { $$ = $1 / $3 ; } 33 | expr '+' expr { $$ = $1 + $3 ; } 34 | expr '-' expr { $$ = $1 − $3 ; } 35 | expr '^' expr { $$ = pow ( $1 , $3) ; } 36 | '(' expr ')' { $$ = $2 ; } 37 ; 38 39 %% 40 41 i n t yyerror ( c h a r * s ) { 42 fprintf ( stderr , "%s\n" , s ) ; 43 r e t u r n 0 ; 44 } 45 46 i n t main ( v o id ) { 47 # i f YYDEBUG 48 yydebug = 1 ; 49 # e n d i f 50 i n t i ; 51 f o r ( i= 0 ; i < SIZE ; i++) 52 symtab[ i ] = 0 ; 53 yyparse ( ) ; 54 r e t u r n 0 ; 55 }

C O

N F ID

E N

T IA

L D

R A

F T10.3. PARSER GENERATION: BISON 305

The following is sample input and output for the extended calculator (> is simply the prompt for input and will be the empty string in your system).

> 2 * (5 - 6);

> print 2 * (5 -6);

-2

> x = 6 / (7- 4);

> x;

> print x ;

> y= 3;

> y + -3 * x;

> print y + - 3 * x;

-3

> print y ^ x;

The syntactic aspects of these enchancements are expressed in the follow- ing context-free grammar in EBNF for calculator sentences:

<program> ::= <program> <stmt> ; \n | <stmt> ; \n

<stmt> ::= <expr> | print <expr> <stmt> ::= <variable> = <expr>

<expr> ::= (<expr>) <integer> ::= 1 | 2 | 3 | . . . |∞ <variable> ::= a | b | c | . . . | z

The unary minus operator (−) has precedence over all other operators. The exponentiation operator (ˆ) is right-associative and has the second highest precedence. Identifiers for single-character variables are limited to the 26 lowercase alphabetic characters.

1 /* y i e l d s an i n t e g e r i n t h e r an g e 0−25 */ 2 /* a s c i i code f o r c h a r a c t e r ' a ' i s 97 */

C O

N F ID

E N

T IA

L D

R A

F T306 CHAPTER 10. AUTOMATIC PROGRAM GENERATION

program output scanner

(regular grammar) grammar) (context−free

tokens parser

source program (string or

list of lexemes)

list of

Front End

interpreter

interpreting while parsing

Figure 10.9: Interpreting while parsing.

calc2.tab.h

tokens

source program

(string or list of lexemes)

list of

Front End

interpreter

interpreting while parsing

program output

(regular grammar) calc2.l scanner lex.yy.c

(context−free grammar) calc2.y

parser calc2.tab.c

Figure 10.10: Interpreting while parsing in calculator (version 1 and 2).

3 /* a s c i i code f o r c h a r a c t e r ' t ' i s 116 */ 4 yylval = *yytext − 'a' ;

The lexical analyzer must now return VARIABLE tokens in addition to INTEGER tokens.

The same Makefile from version 1 can be used for version 2 of the calculator.

(regular grammar) Interpreter

scanner list of

tokens parser grammar)

(context−freesource program (string or

parse tree

Front End

list of lexemes)

program input

program output

Figure 10.11: Interpretation.

C O

N F ID

E N

T IA

L D

R A

F T10.4. PUTTING IT ALL TOGETHER: TOWARDS INTERPRETERS 307

Interpreterscanner source program

(string or list of lexemes)

list of

tokens parser grammar)

(context−free parse tree

Front End

(regular grammar) program output

program input

interpreter (compiled to machine code)

(input to the interpreter)

(e.g., processor)

Figure 10.12: Alternate view of execution by interpretation.

translated program

scanner (regular grammar) list of

tokens parser grammar)source program

(string or parse tree

Front End

list of lexemes)

(context−free

Compiler

Interpreter (e.g., processor)

code generator/ translatoranalyzer

semantic

program output

program input

(e.g., object code)

Figure 10.13: Compilation.

10.4 Putting It All Together: Towards Interpreters

In this section, we extend the language for calculator sentences and its parser. Specifically, we

1. incorporate more features into the calculator,

2. construct a syntax tree during parsing, and

3. traverse the tree to evaluate a calculator program and produce output.

10.4.1 Calculator (version 3)

The additional features are

• the <, <=, >, >=, ==, and ! = binary comparison operators,

• selection through if and if–else statements,

• repetition through a while statement, and

• statement blocks beginning and ending with { and }, respectively.

C O

N F ID

E N

T IA

L D

R A

F T308 CHAPTER 10. AUTOMATIC PROGRAM GENERATION

program output

mul id3 add id4 store id1

001101010110110 000110101010111 111100011100101 010101010101010

id1 = id2 * id3 + id4

scanner

parser

preprocessor

n = x * y + z

id1

Front End

n = x * y + z

code generator

Compiler

/* mathematical expression */

id2 id3

id4 parse tree

assembly code

assembler

object code

source program commented

list of tokens

list of lexemes

processorprogram input

load id2

Figure 10.14: Low-level view of execution by compilation.

(regular grammar) Interpreter

scanner list of

tokens parser grammar)

(context−freesource program (string or

parse tree

Front End

list of lexemes)

program output

Figure 10.15: Calculator expression interpretion.

C O

N F ID

E N

T IA

L D

R A

F T10.4. PUTTING IT ALL TOGETHER: TOWARDS INTERPRETERS 309

program output

list of

tokens

source program (string or

parse tree

Front End

list of lexemes)

(regular grammar)

lex.yy.c

scanner (calc3.l)

calc3.tab.c

(context−free grammar)

(calc3.y)

parser calc3.tab.h

Interpreter

interpreter.c

Figure 10.16: Calculator expression interpretion.

in assembly code

code generator/ translator

Compiler

(context−free

scanner (regular grammar) list of

tokens parser grammar)source program

(string or parse tree

Front End

list of lexemes)

translated program

Figure 10.17: Calculator expression compilation.

calc3.tab.h

code generator/ translator

Compiler

list of

tokens

source program (string or

parse tree

Front End

list of lexemes)

translated program

in assembly code

compiler.c

(regular grammar) (calc3.l)

scanner lex.yy.c

(context−free grammar)

(calc3.y)

calc3.tab.c

parser

Figure 10.18: Calculator expression compilation.

Front End

mul id3 add id4 store id1

id1 = id2 * id3 + id4tokens

scanner

parser

n = x * y + zsource program

id1

code generator

Compiler

id2 id3

id4 parse tree

assembly code

lex

yacc

regular grammar ( ).l

context−free grammar ( ).y

(mathematical expression)

load id2

Figure 10.19: .

C O

N F ID

E N

T IA

L D

R A

F T310 CHAPTER 10. AUTOMATIC PROGRAM GENERATION

Front End

mul id3 add id4 store id1

id1 = id2 * id3 + id4tokens

n = x * y + zsource program

id1

id2 id3

id4

parse tree

assembly code

compiler.c

Compiler

code generator

lex

yacc

calc3.l (regular grammar)

calc3.y (context−free grammar) parser

calc3.tab.h calc3.tab.c

scanner lex.yy.c

(mathematical expression)

load id2

Figure 10.20: .

With these new features, the language understood by the calculator begins to resemble an imperative programming language. These features, which have the same semantics as in C, are expressed in the following context- free grammar in EBNF for calculator programs:

C O

N F ID

E N

T IA

L D

R A

F T10.4. PUTTING IT ALL TOGETHER: TOWARDS INTERPRETERS 311

<program> ::= <code> <code> ::= <code> <stmt> | <stmt> <stmt> ::= ; | print <expr> ;

<stmt> ::= <var> = <expr> ; <stmt> ::= while ( <expr> ) <stmt>

<stmt> ::= if ( <expr> ) <stmt> [ else <stmt> ] <stmt> ::= { <stmt_list> }

<stmt_list> ::= <stmt> | <stmt_list> <stmt> <expr> ::= <integer> | <var> |− <expr>

<expr> ::= <expr> ˆ <expr> | ( <expr> ) <integer> ::= 1 | 2 | 3 | . . . |∞ <variable> ::= a | b | c | . . . | z

The following is a calculator program,

1 x = 1 0 ; 2 while ( x >= 1 ) { 3 print x ; 4 x = x − 1 ; 5 } .

and its output.

Construction of a parse tree requires some preliminary discussion of some constructs and capabilities in C that help facilitate the process.

C O

N F ID

E N

T IA

L D

R A

F T312 CHAPTER 10. AUTOMATIC PROGRAM GENERATION

Listing 10.21: calc3.l.

1 %{ 2 # i n c l u d e "calc3.h"

3 # i n c l u d e "calc3.tab.h"

4 %} 5

6 %option yylineno 7

8 %% 9

10 [ a−z] { /* v a r i a b l e s */ 11 yylval . environI = *yytext − 'a' ; 12 r e t u r n VARIABLE ; } 13

14 0 { yylval . literal = 0 ; 15 r e t u r n INTEGER ; } 16

17 [ 1−9 ] [ 0−9 ] * { /* i n t e g e r s */ 18 yylval . literal = atoi ( yytext) ; 19 r e t u r n INTEGER ; } 20

21 [−^ ( ) < > = + * / ; { } ] { /* s i n g l e−c h a r a c t e r o p e r a t o r s r e t u r n e d a s ←֓ t h e m s e l f */

22 r e t u r n *yytext ; } 23

24 ">=" { /* o t h e r o p e r a t o r s r e t u r n e d a s t o k e n s */ 25 r e t u r n GE ; } 26

27 "<=" r e t u r n LE ; 28 "==" r e t u r n EQ ; 29 "!=" r e t u r n NE ; 30 "while" r e t u r n WHILE ; 31 "if" r e t u r n IF ; 32 "else" r e t u r n ELSE ; 33 "print" r e t u r n PRINT ; 34

35 [ \t\n] { /* i g n o r e w h i t e s p a c e */ ; } 36

37 . yyerror ( "Unknown character") ; 38

39 %% 40

41 i n t yywrap ( void ) { 42 r e t u r n 1 ; 43 }

C O

N F ID

E N

T IA

L D

R A

F T10.4. PUTTING IT ALL TOGETHER: TOWARDS INTERPRETERS 313

Listing 10.22: calc3.y. 1 %{ 2 # i n c l u d e < s t d l i b . h> 3 # i n c l u d e < s t d i o . h> 4 # i n c l u d e < s t d a r g . h> /* p r o v i d e s a c c e s s t o t h e v a r i a b l e argument macros */ 5 # i n c l u d e "calc3.h" 6 # d e f i n e SIZE 26 7 8 PTnode* newOperatorNode( i n t oper , i n t nops , . . . ) ; 9 PTnode* newLiteralOrVariableNode( i n t literalOrVariable , PTnodeFlag flag) ;

10 void freePTnode( PTnode* nodePtr) ; 11 i n t dfs( PTnode* nodePtr) ; 12 13 void yyerror( c h a r * s) ; 14 15 i n t environment[ SIZE ] ; /* e n v ir o n m e n t */ 16 17 e x t e r n i n t yylineno ; 18 19 %} 20 21 /* v a l u e s t a c k w i l l be an a r r a y o f t h e s e YYSTYPE ' s */ 22 %union { 23 i n t literal ; /* l i t e r a l v a l u e */ 24 c h a r environI ; /* e n v ir o n m e n t in de x */ 25 PTnode* nodePtr ; /* node p o i n t e r */ 26 } ; 27 /* g e n e r a t e s t h e f o l l o w i n g : 28 29 t y p e d e f union { 30 i n t l i t e r a l ; 31 c h a r e n v i r o n I ; 32 PTnode * n o de P t r ; 33 } YYSTYPE ; 34 e x t e r n YYSTYPE y y l v a l ; 35 */ 36 /* i n o t h e r words , c o n s t a n t s , v a r i a b l e s , and nodes can 37 be r e p r e s e n t e d by y y l v a l i n t h e p a r s e r ' s v a l u e s t a c k */ 38 39 /* b in ds INTEGER t o i V a l u e i n t h e YYSTYPE union */ 40 /* a s s o c i a t e s t o k e n names w it h c o r r e c t component o f t h e YYSTYPE union */ 41 /* t o g e n e r a t e f o l l o w i n g code */ 42 /* y y l v a l . n o de P t r = n e w Lit e r a lO r V a r i a b l e N o d e ( yyvsp [ 0 ] . l i t e r a l ) ; */ 43 44 %token <literal> INTEGER 45 %token <environI> VARIABLE 46 %token WHILE IF PRINT 47 /* b in ds e x p r t o n o de P t r i n t h e YYSTYPE union */ 48 %type <nodePtr> stmt expr stmtlist 49 50 %nonassoc IFX 51 %nonassoc ELSE 52 %left GE LE EQ NE '>' '<' 53 %left '+' '-' 54 %left '*' '/' 55 %right '^' 56 %nonassoc UMINUS 57 58 %% 59 60 program : code { exit ( 0 ) ; } 61 ; 62 63 code : code stmt { dfs ( $2) ; freePTnode( $2 ) ; } 64 | /* NULL */ 65 66 stmt : ';' { $$ = newOperatorNode( ';' , 2 , NULL , NULL) ; } 67 | expr ';' { $$ = $1 ; } 68 | PRINT expr ';' { $$ = newOperatorNode( PRINT , 1 , $2) ; } 69 | VARIABLE '=' expr ';' { $$ = newOperatorNode( '=' , 2 , 70 newLiteralOrVariableNode( $1 , variableFlag) , $3) ; } 71 | WHILE '(' expr ')' stmt { $$ = newOperatorNode( WHILE , 2 , $3 , $5) ; } 72 | IF '(' expr ')' stmt %prec IFX { $$ = newOperatorNode( IF , 2 , $3 , $5) ; } 73 | IF '(' expr ')' stmt ELSE stmt { $$ = newOperatorNode( IF , 3 , $3 , $5 , $7 ) ; } 74 | '{' stmtlist '}' { $$ = $2 ; } 75 ; 76

C O

N F ID

E N

T IA

L D

R A

F T314 CHAPTER 10. AUTOMATIC PROGRAM GENERATION

Takes advantage of the fact that ints and chars are represented inter- nally as ints.

10.4.2 Helpful C Constructs and Capabilities

We construct the parse tree in a bottom-up fashion. This means that we allocate leaf nodes when variables and integers are reduced. We allocate an internal nodes when operators are reduced. An internal node contains the operator, the number of arguments, and pointers to previously allocated nodes which represent its operands. Two issues arise.

1. We have different types of nodes: internal nodes and leaf nodes, each with different storage requirements.

2. We have multiple types of internal, operator nodes: those for unary, binary, and ternary operators.

We use unions in C and the control C affords the programmer in lay- ing out the memory structures on the help to address the hetergenity of the different types of nodes (i.e., the first issue), and we use functions of variable arguments to help allocate and load internal nodes which have a different number of children pointers depending on the arity of the opera- tor each represents (i.e., the second issue).

unions

1 union { 2 i n t i ; 3 f l o a t f ; 4 c h a r [ 1 6 ] s ; 5 }

Variable Argument Lists

1 void f( i n t nargs , . . . ) { 2 /* t h e d e c l a r a t i o n . . . 3 can o n l y ap p e ar a t t h e end o f an argument l i s t */ 4

5 i n t i , tmp ;

C O

N F ID

E N

T IA

L D

R A

F T10.4. PUTTING IT ALL TOGETHER: TOWARDS INTERPRETERS 315

PTnodeFlag flag

int oper

int nops

pointer to an array of pointers of type

PTnode*

OperatorNode

structPTnode

int literalOrVariable union − could be any 1 of 2

OperatorNode operator1

PTnode** operands

Figure 10.21: structures for parse tree nodes in calculator (version 3).

7 va_list ap ; /* argument p o i n t e r */ 8

9 va_start( ap , narags) ; /* i n i t i a l i z e s ap t o p o i n t t o t h e 10 f i r s t unnamed argument ; 11 v a _ s t a r t must be c a l l e d once 12 b e f o r e ap can be used */ 13

14 f o r ( i= 0 ; i < nargs ; i++) 15 temp = va_arg( ap , i n t ) ; /* r e t u r n s one argument and 16 s t e p s ap t o t h e n e x t argument */ 17 /* t h e s e co n d argument t o v a _ a r g 18 must be a t y p e name s o t h a t 19 v a _ a r g s knows how b i g a s t e p 20 t o t a k e */ 21

22 va_end( ap ) ; /* c l e a n−up ; must be c a l l e d b e f o r e 23 f u n c t i o n r e t u r n s */ 24 }

10.4.3 Structures for Parse Tree Nodes

Header File

We place the datatype definitions for our parse tree in a file named calc.h.

10.4.4 Precedence and Associativity in Calculator (version 3)

C O

N F ID

E N

T IA

L D

R A

F T316 CHAPTER 10. AUTOMATIC PROGRAM GENERATION

PTnode* newLiteralOrVariableNode(int literalOrVariable, PTnodeFlag flag) {

/* copy data */

100

}

called when we see a literal or variable; creates a leaf node in parse tree

PTnode* nodePtr 100

PTnodeFlag flag

int literalOrVariable

Figure 10.22: Node type used for literals and variables (i.e., leaf nodes) in calculator (ver- sion 3).

PTnode* nodePtr

va_list ap

100100

int operatorLiteral

int numOfOperands

PTnode** operands

called when we see an operator; creates an internal node in parse tree

PTnodeFlag flag

PTnode* newOperatorNode(int operatorLiteral, int numOfOperands, ... ) {

}

/* copy data */

OperatorNode operator1

Figure 10.23: Node type used for operators (i.e., internal nodes) in calculator (version 3).

C O

N F ID

E N

T IA

L D

R A

F T10.4. PUTTING IT ALL TOGETHER: TOWARDS INTERPRETERS 317

1 /* v a l u e s t a c k w i l l be an a r r a y o f t h e s e YYSTYPE ' s ; 2 h as n o t h i n g t o do w it h t h e union i n c a l c 3 . h */ 3 %union { 4 i n t literal ; /* i n t e g e r v a l u e */ 5 c h a r environI ; /* e n vir o n me n t i n d e x */ 6 PTnode* nodePtr ; /* node p o i n t e r */ 7 } ; 8 /* g e n e r a t e s t h e f o l l o w i n g : 9

10 t y p e d e f union { 11 i n t l i t e r a l ; 12 c h a r e n v i r o n I ; 13 n o d e P t r * n o d e P t r ; 14 } YYSTYPE ; 15 e x t e r n YYSTYPE y y l v a l ; 16

17 i n o t h e r words , c o n s t a n t s , v a r i a b l e s , and nodes can 18 be r e p r e s e n t e d by y y l v a l i n t h e p a r s e r ' s v a l u e s t a c k 19

20 b i n d s INTEGER t o i V a l u e i n t h e YYSTYPE union 21 a s s o c i a t e s t o k e n names w it h c o r r e c t component o f t h e 22 YYSTYPE union t o g e n e r a t e f o l l o w i n g code 23 y y l v a l . n o d e P t r = n e w L i t e r a l O r V a r i a b l e N o d e ( yyvsp [ 0 ] . l i t e r a l ) ; */ 24

25 %token <literal> INTEGER 26 %token <environI> VARIABLE 27 %token WHILE IF PRINT 28 %nonassoc IFX 29 %nonassoc ELSE 30

31 %left GE LE EQ NE '>' '<' 32 %left '+' '-' 33 %left '*' '/' 34 %right '^' 35 %nonassoc UMINUS 36

37 /* b i n d s e x p r t o n P t r i n t h e YYSTYPE union */ 38 %type <nodePtr> stmt expr stmtlist

10.4.5 Interpreters: Program Evaluators

When the syntax tree is completely built, pass only a pointer to the root node to a function eval which interprets the program and prints any out- put. The eval function returns an int and conducts a depth-first traversal of the tree. Since the tree is constructed in a bottom-up fashion, the depth- first walk visits nodes in the order in which they were allocated. This ap-

C O

N F ID

E N

T IA

L D

R A

F T318 CHAPTER 10. AUTOMATIC PROGRAM GENERATION

interpreter.o

interpreter.c calc.tab.h calc.h

parsetree.o

parsetree.c

calc.tab.o

calc.tab.c

calc.y

compiler.o

compiler.c

lex.yy.o

lex.yy.c

calc.l

all

interpreter compilerparsetree

Figure 10.24: Makefile dependency graph for calculator (version 3).

proach has the attractive property of applying the operators in the order that they were encountered during parsing or, in other words, according to the rules of precedence.

When eval returns, pass only a pointer to the root node of the syntax tree to a function freeTree which frees each node of the tree.

The Makefile dependency graph for calculator (version 3) is given in Fig. 10.24.

10.4.6 Conceptual Exercises for Section 10.4

Exercise 10.4.1: What is the underlying cause of a shift-reduce conflict?

Exercise 10.4.2: What is the underlying cause of a reduce-reduce conflict?

Exercise 10.4.3: What does bison do when it encounters a shift-reduce conflict?

Exercise 10.4.4: What action does bison take when it encounters a shift- reduce conflict?

Exercise 10.4.5: What does bison do when it encounters a reduce-reduce conflict?

Exercise 10.4.6: Give a specific example of a shift-reduce conflict. Show the complete grammar, input string, parse stack, and value stack to clearly il-

C O

N F ID

E N

T IA

L D

R A

F T10.4. PUTTING IT ALL TOGETHER: TOWARDS INTERPRETERS 319

Listing 10.23: Makefile for calculator (version 3).

1 SRC = calc3 2 CC = gcc −g 3 LEX = flex 4 LEX_FLAGS = 5 YACC = bison 6 YACC_FLAGS = −d −t 7

8 all : interpreter compiler parsetree 9 # a l l : i n t e r p r e t e r c o m p i l e r

11 interpreter : lex . yy . o $ ( SRC) . tab . o interpreter . o 12 $ ( CC) −lm lex . yy . o $ ( SRC) . tab . o interpreter. o −o interpreter 13

14 compiler : lex . yy . o $ ( SRC) . tab . o compiler . o 15 $ ( CC) lex . yy . o $ ( SRC) . tab . o compiler . o −o compiler 16

17 parsetree : lex . yy . o $ ( SRC) . tab . o parsetree . o 18 $ ( CC) lex . yy . o $ ( SRC) . tab . o parsetree . o −o parsetree 19

20 lex . yy . o : lex . yy . c $ ( SRC) . tab . h $ ( SRC) . h 21 $ ( CC) −c lex . yy . c 22

23 lex . yy . c : $ ( SRC) . l 24 $ ( LEX) $ ( LEX_FLAGS) $ ( SRC) . l 25

26 $ ( SRC) . tab . o : $( SRC) . tab . c $( SRC) . h 27 $ ( CC) −c $ ( SRC) . tab . c 28

29 $ ( SRC) . tab . c : $( SRC) . y 30 $ ( YACC) $ ( YACC_FLAGS) $ ( SRC) . y 31

32 $ ( SRC) . tab . h : $( SRC) . y 33 $ ( YACC) $ ( YACC_FLAGS) $ ( SRC) . y 34

35 interpreter . o : interpreter . c $ ( SRC) . h $( SRC) . tab . h 36 $ ( CC) −c interpreter . c 37

38 compiler . o : compiler . c $( SRC) . h $ ( SRC) . tab . h 39 $ ( CC) −c compiler . c 40

41 parsetree . o : parsetree . c $( SRC) . h $( SRC) . tab . h 42 $ ( CC) −c parsetree . c 43

44 clean : 45 −rm * . o $ ( SRC) . tab . h $( SRC) . tab . c lex . yy . c interpreter compiler ←֓

parsetree

C O

N F ID

E N

T IA

L D

R A

F T320 CHAPTER 10. AUTOMATIC PROGRAM GENERATION

lustrate the conflict and to convince us that you know what you are talking about.

Exercise 10.4.7: Give a specific example of a shift-reduce conflict. Show a complete BNF grammar, input string, and parse stack to clearly illustrate the conflict. Use . (dot) to denote the top of the stack.

Exercise 10.4.8: Give a specific example of a reduce-reduce conflict. Show the complete grammar, input string, parse stack, and value stack to clearly illustrate the conflict and to convince us that you know what you are talk- ing about.

Exercise 10.4.9: Give a specific example of a reduce-reduce conflict. Show a complete BNF grammar, input string, parse stack, and value stack to clearly illustrate the conflict. Use . (dot) to denote the top of the stack.

Exercise 10.4.10: Consider the following context-free grammar in EBNF. Would this grammar pose a problem bison, even without directives to disambiguate the grammar? Explain why or why not. Be specific.

<stmt> ::= if <expr> <stmt> else <stmt> <stmt> ::= s <expr> ::= c

Exercise 10.4.11: State whether it is preferable or not to use a left-recursive or right-recursive grammar with bison and why. Explain. Be specific.

Exercise 10.4.12: Consider the following ambiguous context-free grammar in EBNF for the dangling else problem. Does this grammar as is, and without directives to disambiguate the grammar, pose a problem for bison? Explain why or why not. Be specific.

where the non-terminal <other> generates some non-if statement such as a print statement.

C O

N F ID

E N

T IA

L D

R A

F T10.4. PUTTING IT ALL TOGETHER: TOWARDS INTERPRETERS 321

Exercise 10.4.13: In version 1 of the calculator, why is the string print -4 - 5 parsed as a sentence, if the unary minus operator has the highest precedence?

Exercise 10.4.14: In version 2 of the calculator, will the ’-’ expr %prec ’ˆ’ { $$ = $2*-1; } rule interfere with parsing the string print 2 ˆ -3;

Exercise 10.4.15: In version 2 of the calculator, what is the difference between ’-’ expr %prec ’ˆ’ { $$ = $2*-1; } and ’-’ expr %prec UMINUS { $$ = $2*-1; }?

10.4.7 Programming Exercises for Section 10.4

Exercise 10.4.16: Consider the following context-free grammar defined in EBNF (from [Lou02]):

<expr> ::= ( <list> ) | a <list> ::= <expr> [<list>]

where <expr> and <list> are non-terminals and a, (, and ) are terminals.

Automatically generate a shift-reduce, bottom-up parser by defining a flex and a bison specification of a parser for the language defined by this grammar. The parser must accepts strings from standard input (one per line) until EOF and determines whether or not each string is in the lan- guage defined by this grammar. Thus, it might be help to think of defining this language using the following context-free grammar in EBNF:

where <sentence>, <expr>, and <list> are non-terminals and a, (, ), and \n are terminals.

Factor your program into a scanner (lexical analyzer) and shift-reduce parser (syntactic analyzer) as shown in Figs. 10.3 and 10.5.

C O

N F ID

E N

T IA

L D

R A

F T322 CHAPTER 10. AUTOMATIC PROGRAM GENERATION

You may not assume that each lexeme will be valid and separated by ex- actly one space, or that each line will contain no leading or trailing whites- pace. There are two distinct error conditions that your program must recognize. First, if a given string does not consist of valid lexemes, then respond with this message: “...” contains invalid lexemes and, thus, is not a sentence. Second, if a given string consists of valid lexemes but it is not a sentence according to the grammar, then re- spond with the message: “...” is not a sentence. Note that the “invalid lexemes” message takes priority over the “not a sentence” mes- sage (i.e., the “not a sentence” message can only be issued if the input string consists entirely of valid lexemes).

You may assume that whitespace is ignored, that no line of input will ex- ceed 4,096 characters, that each line of input will end with a newline, and that no string will contain more than 200 lexemes.

Print only one line of output to standard output per line of input, and do not prompt for input. The following is a sample interactive session with the parser (> is simply the prompt for input and will be the empty string in your system):

> ( a)

"( a )" is a sentence.

> a

"a" is a sentence.

> ( ( ( a a ) ) )

"( ( ( a a ) ) )" is a sentence.

> ( a ) )

"( a ) )" is not a sentence.

> ,(a)

",(a)" contains invalid lexemes and, thus, is not a sentence.

> (( (a a ) ))

"( ( ( a a ) ) )" is a sentence.

> ( a ( a ) ) )

"( a ( a ) ) )" is not a sentence.

> (( a ) 1 )

"(( a ) 1 )" contains invalid lexemes and, thus, is not a sentence.

> (a(a))

"( a ( a ) )" is a sentence.

> ( ( a ) )

"( ( a ) )" is a sentence.

> ( )

"( )" is not a sentence.

C O

N F ID

E N

T IA

L D

R A

F T10.4. PUTTING IT ALL TOGETHER: TOWARDS INTERPRETERS 323

> (

"(" is not a sentence.

You may assume the following code in your bison specification, though you must replace each ... with one line of code:

1 sentence : sentence expr '\n' { printf ( "\"%s\" is a sentence.\n" , 2 temp) ; 3 . . . } 4 | error '\n' { printf ( "\"%s\" is not a sentence.\n" , 5 temp) ; 6 . . . 7 yyclearin ; /* d i s c a r d lo o k ah e ad */ 8 yyerrok ; } 9 |

10 ; 11 /* b i s o n s p e c i f i c a t i o n f i l e p a r s e r . y */

Also write a Makefile which builds your parser. Your Makefile must include target directives for every derived file produced during the com- pilation process (i.e., each program, each object file, and any other inter- mediate files produced during code generation and compilation). Make sure that each directive also lists all files on which the derived file depends in its dependency list. Also, your Makefile must be written to carry out only the commands necessary to bring any produced file up-to-date. Your Makefile must do just enough, but no extra, work to bring the final exe- cutable for your parser up-to-date every time make is invoked. In addition, it must have an all directive and a clean directive to remove all gener- ated files. Use variables where appropriate to improve the readability of your Makefile. Your Makefile must bring everything up-to-date, using only flex, bison, and gcc, without any warnings or errors, when make is invoked.

Exercise 10.4.17: Consider the following context-free grammar defined in EBNF:

::= () | () | ()() | ()

where is a non-terminal and ( and ) are terminals.

C O

N F ID

E N

T IA

L D

R A

F T324 CHAPTER 10. AUTOMATIC PROGRAM GENERATION

Complete Programming Exercise 10.4.16 using this grammar subject to all of the requirements given in that exercise.

The following is a sample interactive session with the parser:

> ()

"()" is a sentence.

> ()()

"()()" is a sentence.

> (())

"(())" is a sentence.

> (()())()

"(()())()" is a sentence.

> ((()())())

"((()())())" is a sentence.

> (a)

"(a)" contains invalid lexemes and, thus, is not a sentence.

> )(

")(" is not a sentence.

> )()

")()" is not a sentence.

> )()(

")()(" is not a sentence.

> (()()

"(()()" is not a sentence.

> ())((

"())((" is not a sentence.

> ((()())

"((()())" is not a sentence.

Exercise 10.4.18: Consider the following context-free grammar defined in EBNF from § 10.3.3:

<expr> ::= <integer> <integer> ::= 1 | 2 | 3 | . . . |∞

where <expr> and <integer> are non-terminals and +, *, −, and 1, 2, 3, . . . are terminals.

Use flex and bison to build a C program which reads sentences in the language defined by this grammar from standard input (one per line) until

C O

N F ID

E N

T IA

L D

R A

F T10.4. PUTTING IT ALL TOGETHER: TOWARDS INTERPRETERS 325

EOF and writes each expression evaluated and decorated with parentheses to indicate the order of operator application to standard output (using the format below, one per line). Normal precedence rules hold: − has the high- est, * has the second highest, and + has the lowest. Assume left-to-right associativity. The following is sample input and output for the expression evaluator (> is simply the prompt for input and will be the empty string in your system):

> 2+3*4

(2+(3*4)) = 14

> 2+3*-4

(2+(3*(-4))) = -10

> -2*3+4

(((-2)*3)+4) = -2

Do not build a parse tree to solve this problem.

Hint: Use an array implementation of a stack which contains elements of type char*. Also, use the sprintf function to convert an integer to a string. For example,

1 c h a r * string_representation_of_an_integer = 2 malloc ( 1 0 * s i z e o f ( * string_representation_of_an_integer) ) ; 3

4 /* p r i n t s t h e i n t e g e r 789 t o 5 t h e s t r i n g v a r i a b l e s t r i n g _ r e p r e s e n t a t i o n _ o f _ a n _ i n t e g e r */ 6 sprintf ( string_representation_of_an_integer, "%d" , 7 8 9 ) ; 7

8 /* n e x t l i n e p r i n t s t h e i n t e g e r 789 t o s t d o u t */ 9 printf ( "%s" , string_representation_of_an_integer) ;

You must explicitly deallocate any memory you explicitly allocate (i.e., your program must not have any memory leaks).

Write a Makefile which builds your expression evaluator. Your Makefile must include target directives for every derived file produced during the compilation process (i.e., each program, each object file, and any other intermediate files produced during code generation and com- pilation). Make sure that each directive also lists all files on which the derived file depends in its dependency list. Also, your Makefile must be written to carry out only the commands necessary to bring any produced

C O

N F ID

E N

T IA

L D

R A

F T326 CHAPTER 10. AUTOMATIC PROGRAM GENERATION

file up-to-date. Your Makefile must do just enough, but no extra, work to bring the final executable for your evaluator up-to-date every time make is invoked. In addition, it must have an all directive and a clean directive to remove all generated files. Use variables where appropriate to improve the readability of your Makefile. Your Makefile must bring everything up-to-date, using only flex, bison, and gcc, without any warnings or errors, when make is invoked.

Exercise 10.4.19: Build a parser to determine the order in which operators of a logical expression are evaluated. Expressions are defined by the fol- lowing context-free grammar in BNF (not EBNF):

<expr> ::= <literal> <literal> ::= t

<literal> ::= f

where t, f, |, &, and ∼ are terminals which represent true, false, or, and, and not, respectively. The following is sample input and output for the expression evaluator (> is simply the prompt for input and will be the empty string in your system).

> f | t & f | ~t

((f | (t & f)) | (~t)) is false.

> ~t | t | ~f & ~f & t & ~t | f

((((~t) | t) | ((((~f) & (~f)) & t) & (~t))) | f) is true.

Notice that you must decorate the parsed expression with parentheses to indicate the order of operator-execution as well as evaluate it. Normal precedence rules hold: ∼ has the highest, & has the second highest, and | has the lowest. Assume left-to-right associativity.

Requirements:

a) Your program must read from standard input and write to standard output. Specifically, your program must read a set of expressions from standard input (one per line) and write the corresponding parenthesized

C O

N F ID

E N

T IA

L D

R A

F T10.4. PUTTING IT ALL TOGETHER: TOWARDS INTERPRETERS 327

expressions (also one per line, in the format used above) to standard output.

b) Write a Makefile as indicated in Programming Exercise 10.4.18.

Exercise 10.4.20: Add a do {...} while (...); loop to the calculator (version 3).

Exercise 10.4.21: Re-instrument version 3 of the calculator so that the integer representing a literal or variable in the PTnode type is wrapped in a struct called LiteralOrVariableNode. Call this approach version 4.

PTnodeFlag flag

PTnode*

int literalOrVariable

structPTnode

union − could be any 1 of 2 LiteralOrVariable literalOrVariable

OperatorNode operator1

OperatorNode

pointer to an array of pointers of type

LiteralOrVariableNode

int oper

int nops

PTnode** operands

LiteralOrVariableNode literalOrVariable

/* copy data */

100

}

called when we see a literal or variable; creates a leaf node in parse tree

PTnode* nodePtr 100

PTnodeFlag flag

PTnode* newLiteralOrVariableNode(int literalOrVariable, PTnodeFlag flag) {

C O

N F ID

E N

T IA

L D

R A

F T328 CHAPTER 10. AUTOMATIC PROGRAM GENERATION

Exercise 10.4.22: Re-instrument version 4 of the calculator created in Programming Exercise 10.4.21 to factor the LiteralOrVariableNode struct into a LiteralNode struct and a VariableNode struct. Similarly, factor the newLiteralOrVariableNode function into newLiteralNode and newVariableNode functions. Call this ap- proach version 5.

PTnodeFlag flag

int variable

VariableNode

PTnode*

structPTnode

OperatorNode

LiteralNode

int literal

− could be any 1 of 3union

OperatorNode operator1

VariableNode variable

LiteralNode literal

int oper

int nops

pointer to an array of pointers of type

called a "variant record"

PTnode** operands

LiteralNode literal

/* copy data */

100

}

PTnode* nodePtr 100

PTnodeFlag flag

called when we see a literal; creates a leaf node in parse tree

PTnode* newLiteralNode(int literal, PTnodeFlag flag) {

C O

N F ID

E N

T IA

L D

R A

F T10.4. PUTTING IT ALL TOGETHER: TOWARDS INTERPRETERS 329

VariableNode variable

/* copy data */

100

}

PTnode* nodePtr 100

PTnodeFlag flag

called when we see a variable; creates a leaf node in parse tree

PTnode* newVariableNode(int variable, PTnodeFlag flag) {

Exercise 10.4.23: Re-instrument version 3 of the calculator to use a dif- ferent design for the OperatorNode struct. Specifically, instead of an a pointer to an array of type PTnode*, make the operands field of the OperatorNode struct be a array of size one of pointers of type PTnode* (as shown below) and dynamically expand it as needed in the newOperatorNode function. Call this approach version 6.

PTnodeFlag flag

int oper

int nops

OperatorNode

structPTnode

int literalOrVariable union − could be any 1 of 2

OperatorNode operator1

(expandable)PTnode* operands[1]

C O

N F ID

E N

T IA

L D

R A

F T330 CHAPTER 10. AUTOMATIC PROGRAM GENERATION

PTnode* nodePtr

va_list ap

100 100

called when we see an operator; creates an internal node in parse tree

PTnodeFlag flag

int operatorLiteral

int numOfOperands

PTnode* operands[1]

(expandable)

PTnode* newOperatorNode(int operatorLiteral, int numOfOperands, ... ) {

}

OperatorNode operator1

Would this approach work if the union was the first field of the PTnode struct rather than the PTnodeFlag enum? Explain.

Exercise 10.4.24: Re-instrument version 4 of the calculator (i.e., Program- ming Exercise 10.4.21) to use the memory design of version 6 (i.e., Pro- gramming Exercise 10.4.23). Call this approach version 7.

Exercise 10.4.25: Re-instrument version 5 of the calculator (i.e., Program- ming Exercise 10.4.22) to use the memory design of version 6 (i.e., Pro- gramming Exercise 10.4.23). Call this approach version 8.

Exercise 10.4.26: Re-instrument version 7 of the calculator (i.e., Program- ming Exercise 10.4.24) to use the memory design depicted below where a the PTnode type is a union of structs rather than a struct containing a union. Call this approach version 9 (a memory overlay approach).

C O

N F ID

E N

T IA

L D

R A

F T10.4. PUTTING IT ALL TOGETHER: TOWARDS INTERPRETERS 331

PTnodeFlag flag

union of struct sPTnode

OperatorNode operator1

(expandable)PTnode* operands[1]

OperatorNode

int oper

int nops

nodeFlag flag

union − could be any 1 of 3LiteralOrVariableNode literalOrVariable

PTnodeFlag flag

LiteralOrVariableNode

int literalOrVariable

Would this approach work if the nodeFlag enum type was not a mem- ber of both the LiteralOrVariableNode and OperatorNode struct types, in addition to being a member of the PTnode struct type? Ex- plain. Would this approach work if the PTnodeFlag enum was the last member of the PTnode union? Explain.

Exercise 10.4.27: Re-instrument version 8 of the calculator (i.e., Program- ming Exercise 10.4.25) to use the memory design depicted in version 9 (i.e., Programming Exercise 10.4.27). Call this approach version 10.

C O

N F ID

E N

T IA

L D

R A

F T332 CHAPTER 10. AUTOMATIC PROGRAM GENERATION

PTnodeFlag flag

union of struct sPTnode

(expandable)PTnode* operands[1]

OperatorNode

int oper

int nops

nodeFlag flag

LiteralNode

int literal

VariableNode

int variable

union − could be any 1 of 4

OperatorNode operator1

VariableNode variable

LiteralNode literal

PTnodeFlag flag

Exercise 10.4.28:

Exercise 10.4.29: Build a graphical user interface in Qt, akin to that shown below, for the interpreter/compiler developed in Programming Project 10.5. See http://hipersayanx.blogspot.com/2013/03/ using-flex-and-bison-with-qt.html for help on using flex and bison with Qt.

http://hipersayanx.blogspot.com/2013/03/using-flex-and-bison-with-qt.html