1、YACC2019 Spring&Summer5.5 Yacc: LALR(1) PARSING GENERATORYacc takes a specification file (usually with a .y suffix) produces an output file consisting of C source code for the parser (usually in a file called y.tab.c or ytab.c)A Yacc specification file has the basic format definitions%rules%auxiliar

2、y routines How YACC WorksAn YACC File Example%#include%token NAME NUMBER%statement: NAME = expression| expression; printf(“=%dn”,$1); expression: expression + NUMBER $ = $1 + $3; |Expression - NUMBER $ = $1 - $3;NUMBER $ = $1; ;%int yyerror(char *s)fprintf(stderr, %sn, s);return 0;int main(void)yypa

3、rse();return 0;Works with LEXCommunication between LEX and YACC5.5 Yacc: LALR(1) PARSING GENERATORexp exp addop term | termaddop + | -term term mulop factor | factormulop *factor ( exp ) | number5.5 Yacc: LALR(1) PARSING GENERATOR%#include #include %token NUMBER%command : exp printf (“%dn”,$1); ; /*

4、allows printing of the result */exp: exp + term $ = $1 + $3; | exp - term $ = $1 - $3; | term $ = $1; ;term: term * factor $ = $1* $3; | factor $ = $1; ;factor :NUMBER $ = $1; | ( exp ) $=$2; ;% 5.5 Yacc: LALR(1) PARSING GENERATORmain ( ) return yyparse( ); int yylex(void) int c; while( ( c = getcha

5、r ( ) )= ); /*eliminates blanks */ if ( isdigit(c) ) unget (c,stdin) ; scanf (“%d”,&yylval ) ; return (NUMBER ) ;if (c= n) return 0;/* makes the parse stop */return ( c ) ;5.5 Yacc: LALR(1) PARSING GENERATORint yyerror (char * s) fprintf (stderr, “%sn”,s ) ;return 0;/* allows for printing of an erro

6、r message */5.5 Yacc: LALR(1) PARSING GENERATORTwo ways of recognizing tokens:1.Any character inside single quotes in a grammar rule will be recognized as itself.2. Symbolic tokens may be declared in a YACC %token declaration .%token NUMBER %start symbol (define the start symbol .)3.Action code is p

7、laced at the end of each grammar rule choice, although it is also possible to write embedded actions within a choice.5.5 Yacc: LALR(1) PARSING GENERATOR4. Take advantage of Yacc pseudovariables.When a grammar rule is recognized, each symbol in the rule possesses a value, which is assumed to be an in

8、teger unless changed by the programmer. These values are kept on a value stack by Yacc.the Yacc pseudovariables in the specification fileThis data type is always defined in Yacc by the C perprocessor symbol YYSTYPE. #define YYSTYPE double inside the brackets % . . .% in the definition section of the

9、 Yacc specification file. 5.5 Yacc: LALR(1) PARSING GENERATORDifferent values for different grammar rules.exp exp addop term | termaddop + | -There are two ways to do this. (1)Declare the union directly in the Yacc specification using the %union Yacc declaration:%union double val; char op; 5.5 Yacc:

10、 LALR(1) PARSING GENERATOR%token NUMBER%union double val; char op;%type exp term factor NUMBER%type addop mulop%command : exp printf(“%dn”,$1); ;exp : exp op term switch ($2); case + : $=$1+$3; break; case - : $=$1 - $3; break; | term $ = $1; ;5.5 Yacc: LALR(1) PARSING GENERATOR(2)The second alterna

11、tive ： Define a new data type in a separate include file define YYSTYPE to be this type. the appropriate values must be constructed by hand in the associated action code. 5.5 Yacc: LALR(1) PARSING GENERATOR5. All nonterminals achieve their values by such user-supplied actions. Tokens may also be ass

12、igned values, this is done during the scanning process. Yacc assumes that the value of a token is assigned to the variable yylval.5.5 Yacc: LALR(1) PARSING GENERATOR6.In the third section, yyparse is declared to return an integer value, which is 0 if the parse succeeds, and 1 if it does not. The yyp

13、arse procedure calls a scanner procedure( yylex. ) Yacc expects the end of input to be signaled by a return of the null value 0 by yylex. The yyerror procedure prints an error message when an error is encountered during the parse. 5.5 Yacc: LALR(1) PARSING GENERATORIt is necessary to execute some co

14、de prior to the complete recognition of a grammar rule choice during parsing. decl type var-listtype int | floatvar-list var-list, id | id 5.5 Yacc: LALR(1) PARSING GENERATORdecl : type current_type=$1 var-list ;type : INT $=INT_TYPE; | FLOAT $=FLOAT_TYPE; ;var_list :var_list , ID setType(tokenStrin

15、g,current_type); |ID setType(tokenString,current_type); ; 5.5 Yacc: LALR(1) PARSING GENERATORYacc interprets an embedded actionA : B /* embedded action */ C ; A : B E C ;E: /* embedded action */ 5.5 Yacc: LALR(1) PARSING GENERATORYacc has disambiguating rules built into it Yacc disambiguates by pref

16、erring the reduction by the grammar rule listed first in the specification file. %left + -%left * (specified in the definitions ) the operators + and - have the same precedence and are left associative the operator * is left associative and has higher precedence than + and - 5.6 GENERATION OF A TINY

17、 PARSER USING YaccThe syntax of TINY was given in Section 3.7.A handwritten parser was described in Section 4.4. the Yacc specification file tiny.y, the global definitions globals.h The entire tiny.y file is listed in Appendix B. lines 4000-4162.The definitions section of the Yacc specification of T

18、INY:1. There are four #include files, representing the information needed by Yacc from elsewhere in the program (lines.4009-4012). 2.The definitions section has four other declarations. (1) The first (line 4014) is a definition of YYSTYPE, which defines the values returned by Yacc parsing procedures

19、 to be pointers to node structures (TreeNode itself is defined in globals .h). This allows the Yacc parser to construct a syntax tree. (2) The second declaration is of a static global savedName variable, which is used to temporarily store identifier strings that need to be inserted in tree nodes tha

20、t are not yet constructed when the strings are seen in the input (in TINY this is only necessary in assignments). (3) The variable savedLineNo is used for the same purpose. (4) savedTree is used to temporarily store the syntax tree produced by the yyparse procedure (yyparse itself can only return an

21、 integer flag).2. The actions associated with each of the grammar rules of TINY: (these rules are slight variations of the BNF grammar given in Chapter 3, Figure 3.6). In most cases these actions represent the construction of the syntax tree corresponding to the parse tree at that point. (1) new nod

22、es need to be allocated by calls to newStmtNode and newExpNode from the util package (these were described on page 182), and appropriate child nodes of the new tree node need to be assigned. For example, the actions corresponding to the TINY write-stmt (lines 4082) are as follows:write-stmt : WRITE

23、exp $=newStmtNode(WriteK);$-child0=$2;The first instruction calls newStmtNode and assigns its returned value as the value of the write-stmt. Then it assigns the previously constructed value of exp (the Yacc pseudovariable $2, which is a pointer to the tree node of the expression to be printed) to be

24、 the first child of the tree node of the write statement. The action code for other statements and expressions is quite similar.(2) The actions for program, stmt-seq, and assign_stmt deal with small problems associated with each of these constructs. In the case of the grammar rule for program, the a

25、ssociated action (line 4029) is savedTree=$1;This assigns the tree constructed for the stmt-seq to the static variable savedTree. This is necessary so that the syntax tree can later be returned by the parse procedure.(3) The assign_stmt:We have already mentioned that we need to store the identifier

26、string of the variable that is the target of the assignment so that it will be available when the node is constructed (as well as its line number for later tracing). This is achieved by using the static savedName and savedLineNo variables (lines 4067):assign_stmt : ID savedName=copyString(tokenStrin

27、g);savedlineNo = lineno;ASSIGN exp $ = newStmtNode(AssignK) ; $-child 0 = $4; $- = savedName; $-lineno = saveLineNo;The identifier string and line number must be saved as an embedded action before the recognition of the ASSIGN token, since as new tokens are matched, the values of tokenString and lin

28、eno are changed by the scanner.Yet the new node for the assignment cannot be fully constructed until the exp is recognized. Hence, the need for savedName and saveLineNo. (The use of the utility procedure copyString ensures no sharing of memory for these strings.)Note also that the exp value is refer

29、red to as $4. This is because Yacc counts embedded actions as additional places in the right-hand sides of grammar rules.(4) The stmt-seq (lines 4031-4039).The statements are strung together in a TINY syntax tree using sibling pointers instead of child pointers. The rule for statement sequences is w

30、ritten left recursively.This requires that the code chase down the already constructed sibling list for the left sub-list in order to attach the current statement at the end. This is inefficient and can be avoided by rewriting the rule right recursively, but this solution has its own problem, in tha

31、t the parsing stack will grow large as long statement sequences are processed.2. the auxiliary procedure section of the Yacc specification (lines 4144-4162).The definition of three procedures, yyerror. yylex, and parse. The parse procedure, which is called from the main program, calls the Yacc-generated parse procedure yyparse and then returns the saved syntax tree.The yylex procedure is needed because Yacc assumes this is the name of the scanner procedure, and this was defined externally as g