语法分析器——哈工大编译原理课程(二)

一、语法分析器的工作流程为:每次从词法分析器产生的lex.txt文件中读取一个单词符号,根据预测分析表以及状态(整型)栈、符号(token结构体类型)栈的栈顶决定执行移进/规约/接受/error动作。

  1 #include <stdio.h>
  2 #include <stdlib.h>
  3 #include <string.h>
  4 #include <table.h>
  5 #include <stack.h>
  6 
  7 stack s1;
  8 stack s2;
  9 pstack state = &s1;
 10 pstack symbol = &s2;
 11 FILE *fp;   //获取文件的指针
 12 int newflag = 0;        //标志是否新读入一个token
 13 
 14 int ReadToken();    /*make(返回结构体)从文件中读取一行,返回数字*/
 15 void Reduction_Goto(int k);     /*按第k个产生式规约*/
 16 
 17 int main()
 18 {
 19     int token;      /*种别码*/
 20     int index;
 21     int statenum;
 22     int tokennum;
 23     MakeNull(state);
 24     MakeNull(symbol);
 25     fp = fopen("lex.txt","r");
 26 
 27     push(state,0);
 28     push(symbol,0);
 29     printf("stack				production");
 30 
 31     while(1)
 32     {
 33         printf("
");
 34         PrintStack(state,0);
 35         printf("%c",'&');
 36         PrintStack(symbol,1);
 37 
 38         if(newflag == 0)
 39         {
 40             token = ReadToken();
 41         }
 42         /*printf("token:%d",token);*/
 43         statenum = state->elem[state->top];
 44         tokennum = yytranslate[token];
 45 
 46         if(yypact[statenum] == YYPACT_NINF)     /*按默认产生式规约*/
 47         {
 48             if(yydefact[statenum] == 0)
 49             {
 50                 printf("
error!
");
 51                 break;
 52             }
 53             else if(yydefact[statenum] == 1)
 54             {
 55                 printf("
accept!
");
 56                 break;
 57             }
 58             else
 59             {
 60                 Reduction_Goto(yydefact[statenum]);
 61                 newflag = 1;
 62             }
 63         }
 64         else
 65         {
 66             index = yypact[statenum] + tokennum;
 67             /*printf("index:%d",index);*/
 68             if((index >= LCHECK) || (yycheck[index] != tokennum)) /*按默认产生式规约*/
 69             {
 70                 if(yydefact[statenum] == 0)
 71                 {
 72                     printf("
error!
");
 73                     break;
 74                 }
 75                 else if(yydefact[statenum] == 1)
 76                 {
 77                     printf("
accept!
");
 78                     break;
 79                 }
 80                 else
 81                 {
 82                     Reduction_Goto(yydefact[statenum]);
 83                     newflag = 1;
 84                 }
 85             }
 86             else
 87             {
 88                 if(yytable[index] == YYTABLE_NINF)
 89                 {
 90                     printf("
error!
");
 91                     break;
 92                 }
 93                 else if(yytable[index] == 0)
 94                 {
 95                     if(yydefact[statenum] == 0)
 96                     {
 97                         printf("
error!
");
 98                         break;
 99                     }
100                     else if(yydefact[statenum] == 1)
101                     {
102                         printf("
accept!
");
103                         break;
104                     }
105                     else
106                     {
107                         Reduction_Goto(yydefact[statenum]);
108                         newflag = 1;
109                     }
110                 }
111                 else if(yytable[index] < 0)
112                 {
113                     Reduction_Goto(-yytable[index]);    /*按产生式规约,变负*/
114                     newflag = 1;
115                 }
116                 else
117                 {
118                     push(state,yytable[index]);
119                     push(symbol,tokennum);
120                     newflag = 0;
121                 }
122             }
123         }
124     }
125 
126     fclose(fp);
127     return 0;
128 }
129 int ReadToken()
130 {
131     char strLine[1024];
132     char n1[10];
133     int i;
134     if(feof(fp)||(NULL == fgets(strLine,1024,fp)))
135     {
136         return 0;
137     }
138     for(i=1;;i++)
139     {
140         if(strLine[i] == ',')
141         {
142             n1[i-1] = '';
143             return atoi(n1);
144             /*break;*/
145         }
146         n1[i-1] = strLine[i];
147     }
148     /*return 0;*/
149     /*printf("%d",atoi(n1));*/
150     /*return atoi(n1);*/
151 }
152 
153 void Reduction_Goto(int k)      /*按第k个产生式规约,k为正数*/
154 {
155     /*printf("shizi:%d",k);*/
156     int len = yyr2[k];
157     int array[len];
158     int i,index;
159     int symbolnum,statenum;
160 
161     for(i = 0;i < len;i++)
162     {
163         pop(state);
164     }
165     for(i = 0;i < len;i++)
166     {
167         array[i] = pop(symbol);
168     }
169     push(symbol,yyr1[k]);
170 
171     printf("  ");           /*begin打印产生式*/
172     printf("&&%s",yytname[yyr1[k]]);
173     printf("%s","->");
174     for(i = len - 1 ;i >= 0;i--)
175     {
176         printf("%s ",yytname[array[i]]);
177     }                      /*end*/
178 
179     printf("
");
180     PrintStack(state,0);
181     printf("%c",'&');
182     PrintStack(symbol,1);
183 
184     symbolnum = symbol->elem[symbol->top] - TN;
185     statenum = state->elem[state->top];
186 
187     if(yypgoto[symbolnum] == YYPACT_NINF)
188     {
189         push(state,yydefgoto[symbolnum]);
190     }
191     else
192     {
193         index = yypgoto[symbolnum] + statenum;
194         if((index >= LCHECK) || (yycheck[index] != statenum))
195         {
196             push(state,yydefgoto[symbolnum]);
197         }
198         else
199         {
200             push(state,yytable[index]);
201         }
202     }
203 }
GrammarParser
 1 #define N 1000
 2 
 3 typedef struct{      //整型栈
 4     int top;
 5     int elem[N];
 6 }stack;
 7 typedef stack* pstack;
 8 
 9 typedef struct{      //整型栈
10     int top;
11     symtbl* elem[N];
12 }sstack;
13 typedef sstack* psstack;
14 
15 void MakeNull(pstack S)
16 {
17     S->top = N ;
18 }
19 
20 void push(pstack S,int opd)
21 {
22     if(S->top == 0)
23     {
24         return ;
25     }
26     S->top--;
27     S->elem[S->top] = opd;
28 }
29 
30 int pop(pstack S)
31 {
32     int ret = S->elem[S->top];
33     S->top++;
34     return ret;
35 }
36 
37 void PrintStack(pstack S,int ctrl)   /*没打印空行*/
38 {
39     int i;
40     if(ctrl == 0)       //打印状态栈
41     {
42         for(i = N-1;i >= S->top;i--)
43         {
44             printf("%d ",S->elem[i]);
45         }
46     }
47     else                //打印符号栈
48     {
49         for(i = N-1;i >= S->top;i--)
50         {
51             printf("%s ",yytname[S->elem[i]]);
52         }
53     }
54 }
55 
56 void MakeNulls(psstack S)
57 {
58     S->top = N ;
59 }
60 
61 void pushs(psstack S,symtbl* opd)
62 {
63     if(S->top == 0)
64     {
65         return ;
66     }
67     S->top--;
68     S->elem[S->top] = opd;
69 }
70 
71 void pops(psstack S)
72 {
73     S->top++;
74 }
stack.h
  1 #define TN 67      /*终结符数,不含accept!!!*/
  2 #define LCHECK 551 /*make check表长度*/
  3 
  4 typedef int yytype_uint8;
  5 typedef int yytype_int16;
  6 
  7 static const yytype_uint8 yytranslate[] =               /*token[0]=0!!!!必须的*/
  8 {
  9     0,3,4,44,6,10,12,13,16,17,18,
 10     45,21,23,25,28,29,30,36,37,38,
 11     40,41,43,47,48,51,52,55,59,60,
 12     61,62,64,65,66,27,11,50,7,46,
 13     35,57,56,19,34,26,32,24,39,33,
 14     53,9,42,14,15,8,5,54,63,58,
 15     31,49,22,20
 16 };/*种别码和符号数的对应关系*/
 17 
 18 static const char *const yytname[] =
 19 {
 20   "$end", "error", "$undefined", "AND", "ARRAY", "ASSIGNMENT", "CASE",
 21   "CHARACTER_STRING", "COLON", "COMMA", "CONST", "DIGSEQ", "DIV", "DO",
 22   "DOT", "DOTDOT", "DOWNTO", "ELSE", "END", "EQUAL", "EXTERNAL", "FOR",
 23   "FORWARD", "FUNCTION", "GE", "GOTO", "GT", "IDENTIFIER", "IF", "IN",
 24   "LABEL", "LBRAC", "LE", "LPAREN", "LT", "MINUS", "MOD", "NIL", "NOT",
 25   "NOTEQUAL", "OF", "OR", "OTHERWISE", "PACKED", "PBEGIN", "PFILE", "PLUS",
 26   "PROCEDURE", "PROGRAM", "RBRAC", "REALNUMBER", "RECORD", "REPEAT",
 27   "RPAREN", "SEMICOLON", "SET", "SLASH", "STAR", "STARSTAR", "THEN", "TO",
 28   "TYPE", "UNTIL", "UPARROW", "VAR", "WHILE", "WITH", "$accept", "file",
 29   "program", "muldec_m1", "program_heading", "identifier_list", "block",
 30   "label_declaration_part", "label_list", "label",
 31   "constant_definition_part", "constant_list", "constant_definition",
 32   "cexpression", "csimple_expression", "cterm", "cfactor",
 33   "cexponentiation", "cprimary", "constant", "sign", "non_string",
 34   "type_definition_part", "type_definition_list", "type_definition",
 35   "type_denoter", "new_type", "new_ordinal_type", "enumerated_type",
 36   "subrange_type", "new_structured_type", "structured_type", "array_type",
 37   "index_list", "index_type", "ordinal_type", "component_type",
 38   "record_type", "record_section_list", "record_section", "variant_part",
 39   "variant_selector", "variant_list", "variant", "case_constant_list",
 40   "case_constant", "tag_field", "tag_type", "set_type", "base_type",
 41   "file_type", "new_pointer_type", "domain_type",
 42   "variable_declaration_part", "variable_declaration_list",
 43   "variable_declaration", "procedure_and_function_declaration_part",
 44   "proc_or_func_declaration_list", "proc_or_func_declaration",
 45   "procedure_declaration", "muldec_m2", "procedure_heading", "directive",
 46   "formal_parameter_list", "formal_parameter_section_list",
 47   "formal_parameter_section", "value_parameter_specification",
 48   "variable_parameter_specification", "procedural_parameter_specification",
 49   "functional_parameter_specification", "procedure_identification",
 50   "procedure_block", "function_declaration", "function_heading",
 51   "result_type", "function_identification", "function_block",
 52   "statement_part", "compound_statement", "statement_sequence",
 53   "statement", "open_statement", "closed_statement",
 54   "non_labeled_closed_statement", "non_labeled_open_statement",
 55   "repeat_statement", "open_while_statement", "closed_while_statement",
 56   "open_for_statement", "closed_for_statement", "open_with_statement",
 57   "closed_with_statement", "open_if_statement", "closed_if_statement",
 58   "assignment_statement", "variable_access", "indexed_variable",
 59   "index_expression_list", "index_expression", "field_designator",
 60   "procedure_statement", "params", "actual_parameter_list",
 61   "actual_parameter", "goto_statement", "case_statement", "case_index",
 62   "case_list_element_list", "case_list_element", "otherwisepart",
 63   "control_variable", "initial_value", "direction", "final_value",
 64   "record_variable_list", "boolean_expression", "expression",
 65   "simple_expression", "term", "factor", "exponentiation", "primary",
 66   "unsigned_constant", "unsigned_number", "unsigned_integer",
 67   "unsigned_real", "function_designator", "set_constructor",
 68   "member_designator_list", "member_designator", "addop", "mulop", "relop",
 69   "identifier", "semicolon", "comma", 0
 70 };
 71 
 72 static const yytype_uint8 yyr1[] =
 73 {
 74        0,    67,    68,    69,    70,    71,    71,    72,    72,    73,
 75       74,    74,    75,    75,    76,    77,    77,    78,    78,    79,
 76       80,    80,    81,    81,    82,    82,    83,    83,    84,    84,
 77       85,    85,    85,    85,    86,    86,    86,    87,    87,    88,
 78       88,    88,    89,    89,    90,    90,    91,    92,    92,    93,
 79       93,    93,    94,    94,    95,    96,    97,    97,    98,    98,
 80       98,    98,    99,   100,   100,   101,   102,   102,   103,   104,
 81      104,   104,   105,   105,   106,   107,   107,   107,   108,   108,
 82      109,   109,   110,   110,   110,   111,   111,   112,   112,   113,
 83      114,   115,   116,   117,   118,   119,   120,   120,   121,   121,
 84      122,   123,   123,   124,   124,   125,   125,   126,   126,   127,
 85      128,   128,   129,   129,   130,   131,   131,   132,   132,   132,
 86      132,   133,   134,   135,   136,   137,   138,   139,   139,   139,
 87      140,   140,   141,   142,   143,   144,   145,   146,   146,   147,
 88      147,   148,   148,   149,   149,   150,   150,   150,   150,   150,
 89      150,   150,   150,   150,   150,   150,   151,   151,   151,   151,
 90      152,   153,   154,   155,   156,   157,   158,   159,   159,   160,
 91      161,   162,   162,   162,   162,   163,   164,   164,   165,   166,
 92      167,   167,   168,   169,   169,   170,   170,   170,   171,   172,
 93      172,   172,   172,   173,   174,   174,   175,   176,   176,   177,
 94      178,   179,   179,   180,   181,   181,   182,   183,   183,   184,
 95      184,   185,   185,   186,   186,   187,   187,   188,   188,   188,
 96      188,   188,   188,   189,   189,   189,   190,   190,   191,   192,
 97      193,   194,   194,   195,   195,   196,   196,   197,   197,   197,
 98      198,   198,   198,   198,   198,   199,   199,   199,   199,   199,
 99      199,   199,   200,   201,   202
100 };
101 
102 /* YYR2[YYN] -- Number of symbols composing right hand side of rule YYN.  */
103 static const yytype_uint8 yyr2[] =
104 {
105        0,     2,     1,     5,     0,     2,     5,     3,     1,     6,
106        3,     0,     3,     1,     1,     2,     0,     2,     1,     4,
107        1,     3,     1,     3,     1,     3,     2,     1,     1,     3,
108        1,     3,     1,     2,     1,     2,     1,     1,     1,     1,
109        1,     1,     2,     0,     2,     1,     4,     1,     1,     1,
110        1,     1,     1,     1,     3,     3,     1,     2,     1,     1,
111        1,     1,     6,     3,     1,     1,     1,     1,     1,     3,
112        5,     3,     3,     1,     3,     5,     4,     0,     3,     1,
113        3,     1,     5,     7,     5,     3,     1,     1,     3,     1,
114        1,     3,     1,     3,     2,     1,     3,     0,     3,     1,
115        3,     2,     0,     3,     1,     1,     1,     3,     4,     0,
116        1,     2,     1,     1,     3,     3,     1,     1,     1,     1,
117        1,     3,     4,     1,     1,     2,     1,     3,     3,     3,
118        4,     5,     1,     2,     1,     1,     3,     3,     1,     1,
119        1,     3,     1,     3,     1,     1,     1,     1,     1,     1,
120        1,     1,     1,     1,     1,     0,     1,     1,     1,     1,
121        4,     4,     4,     8,     8,     4,     4,     4,     6,     6,
122        3,     1,     1,     1,     2,     4,     3,     1,     1,     3,
123        2,     1,     3,     3,     1,     1,     3,     5,     2,     5,
124        6,     8,     9,     1,     3,     1,     3,     1,     2,     1,
125        1,     1,     1,     1,     3,     1,     1,     1,     3,     1,
126        3,     1,     3,     2,     1,     1,     3,     1,     1,     1,
127        1,     3,     2,     1,     1,     1,     1,     1,     1,     1,
128        2,     3,     2,     3,     1,     3,     1,     1,     1,     1,
129        1,     1,     1,     1,     1,     1,     1,     1,     1,     1,
130        1,     1,     1,     1,     1
131 };
132 
133 static const yytype_uint8 yydefact[] =
134 {
135        0,     0,     0,     2,     0,   252,     5,     1,   253,     4,
136        0,    11,     0,     8,     0,     0,    16,   254,     6,     0,
137       14,     0,    13,     3,     0,    43,     7,    10,     0,    15,
138       18,     0,     0,    97,    12,    17,     0,    42,    45,     0,
139        0,   102,   224,   228,     0,    38,   225,     0,    37,   229,
140        0,    20,    22,    24,    27,    28,     0,    32,   223,   226,
141      227,    30,    44,     0,     0,     0,    99,     0,     0,     0,
142        0,   104,   105,     0,   110,   106,     0,     0,     0,    33,
143       19,   245,   250,   248,   251,   249,   247,   238,   246,   239,
144      237,     0,     0,   244,   242,   243,   241,   240,     0,     0,
145       26,     0,    36,    39,     0,     0,     0,    41,    77,     0,
146        0,     0,     0,    34,     0,    48,    49,    52,    53,    50,
147       56,    58,    59,    60,    61,    51,    47,     0,    96,   133,
148      125,   155,     9,   135,   101,   109,     0,   111,    11,    11,
149       31,    23,    21,    25,    29,     0,     0,    57,     0,     0,
150        0,     0,    73,     0,     0,    94,    95,     0,    35,    40,
151       46,   100,    98,     0,     0,     0,     0,     0,     0,   155,
152        0,     0,     0,   148,     0,   138,   139,   140,   144,   142,
153      150,   158,   153,   159,   154,   156,   151,   157,   152,   145,
154        0,   172,   173,   146,   147,   149,   171,   103,   113,   112,
155       11,   107,     0,     0,     0,   123,     0,   116,   117,   118,
156      119,   120,   124,   134,   127,   129,   128,    66,     0,    64,
157       65,    67,    54,    68,    93,     0,     0,    79,    89,     0,
158       69,    77,    71,    92,    91,    55,   130,   132,     0,     0,
159        0,     0,     0,   217,     0,   193,   207,   209,   211,   214,
160      215,   218,   219,   220,   171,     0,   199,   188,     0,   206,
161        0,     0,   205,     0,   171,   155,   136,   155,     0,     0,
162        0,   174,     0,   180,   126,   108,     0,     0,     0,   114,
163        0,     0,     0,     0,     0,    74,    72,     0,   131,   232,
164      236,     0,   234,     0,   222,   213,     0,     0,     0,     0,
165        0,   230,     0,   155,     0,   155,   155,     0,   143,   141,
166      137,   170,   179,     0,   177,   178,     0,   184,   185,     0,
167      121,   115,     0,    63,    87,    76,    81,     0,    86,    78,
168       90,    70,   231,     0,     0,   221,     0,     0,   195,   210,
169      208,   212,   216,     0,   200,   167,   140,   160,   161,   162,
170      165,   166,   204,   175,     0,   182,     0,     0,   122,    62,
171        0,    75,     0,     0,   233,   235,   155,   189,   253,     0,
172      202,   201,     0,   155,   176,   183,   186,    88,    80,    77,
173       85,   196,   190,   197,   194,   155,     0,   203,   168,   169,
174        0,     0,     0,   198,     0,   155,   187,    82,    77,    84,
175      191,     0,   163,   164,     0,   192,    83
176 };
177 
178 /* YYDEFGOTO[NTERM-NUM].  */
179 static const yytype_int16 yydefgoto[] =
180 {
181       -1,     2,     3,    11,     4,   150,   213,    16,    21,   172,
182       25,    29,    30,    50,    51,    52,    53,    54,    55,   111,
183      242,   113,    33,    37,    38,   223,   115,   116,   117,   118,
184      119,   120,   121,   218,   219,   220,   224,   122,   151,   152,
185      153,   225,   325,   326,   327,   328,   226,   227,   123,   234,
186      124,   125,   155,    41,    65,    66,    69,    70,    71,    72,
187      200,    73,   201,   164,   206,   207,   208,   209,   210,   211,
188       74,   275,    75,    76,   236,    77,   215,   132,   173,   174,
189      175,   176,   177,   178,   179,   180,   181,   182,   183,   184,
190      185,   186,   187,   188,   189,   243,   191,   313,   314,   192,
191      193,   273,   316,   317,   194,   195,   244,   337,   338,   385,
192      255,   343,   372,   386,   263,   258,   259,   246,   247,   248,
193      249,   250,   251,    58,    59,    60,   252,   253,   291,   292,
194       91,    98,    92,   254,   267,    19
195 };
196 /* YYPACT[STATE-NUM] -- Index in YYTABLE of the portion describing
197    STATE-NUM.  */
198 #define YYPACT_NINF -286
199 static const yytype_int16 yypact[] =
200 {
201        1,    27,    69,  -286,    34,  -286,    67,  -286,  -286,  -286,
202       27,    87,    25,  -286,   109,   115,   113,  -286,  -286,    27,
203     -286,     6,  -286,  -286,    27,    70,  -286,  -286,   109,    27,
204     -286,   118,    27,    96,  -286,  -286,   439,    27,  -286,   147,
205       27,   180,  -286,  -286,   439,  -286,  -286,   446,  -286,  -286,
206       34,   504,   131,  -286,  -286,   150,   439,  -286,  -286,  -286,
207     -286,  -286,  -286,   372,   171,    34,  -286,    27,    27,   167,
208       34,  -286,  -286,    34,   185,  -286,    34,    34,   168,  -286,
209     -286,  -286,  -286,  -286,  -286,  -286,  -286,  -286,  -286,  -286,
210     -286,   439,   439,  -286,  -286,  -286,  -286,  -286,   439,   446,
211     -286,   200,  -286,  -286,    27,    73,   195,  -286,    11,   213,
212       27,   240,   114,  -286,    34,  -286,  -286,  -286,  -286,  -286,
213     -286,  -286,  -286,  -286,  -286,  -286,   242,   372,    27,   186,
214     -286,   288,  -286,  -286,   180,    88,   182,  -286,   222,    87,
215     -286,   131,   179,  -286,  -286,   331,    28,  -286,   372,    27,
216      173,    22,  -286,   247,   331,  -286,  -286,   481,  -286,  -286,
217     -286,  -286,  -286,    27,   259,   414,    27,   109,   414,   288,
218      414,    27,   261,  -286,    65,  -286,  -286,  -286,  -286,  -286,
219     -286,  -286,  -286,  -286,  -286,  -286,  -286,  -286,  -286,  -286,
220       51,  -286,  -286,  -286,  -286,  -286,   189,  -286,  -286,  -286,
221       87,  -286,    27,    27,   183,  -286,   146,  -286,  -286,  -286,
222     -286,  -286,  -286,  -286,  -286,  -286,  -286,  -286,    24,  -286,
223     -286,   242,  -286,  -286,  -286,   238,   268,  -286,   248,   372,
224     -286,    11,  -286,  -286,  -286,  -286,  -286,  -286,    27,   393,
225      414,   460,   414,    75,   249,  -286,   504,   131,  -286,  -286,
226      229,  -286,  -286,  -286,   257,   275,  -286,  -286,   232,  -286,
227       -9,   279,    75,   236,  -286,   346,  -286,   288,   414,    27,
228      414,  -286,   414,  -286,  -286,  -286,   186,   239,    27,  -286,
229      182,   256,   331,   481,    27,  -286,  -286,   280,  -286,  -286,
230     -286,    43,   278,   244,  -286,  -286,   481,   414,   414,   414,
231      460,  -286,   414,   288,   414,   288,   288,    27,  -286,  -286,
232     -286,  -286,  -286,    55,  -286,  -286,    32,  -286,   292,    27,
233     -286,  -286,   372,  -286,   286,    34,  -286,   251,  -286,  -286,
234     -286,  -286,  -286,   414,   414,  -286,   253,   156,  -286,   131,
235      179,  -286,  -286,    42,  -286,  -286,   290,  -286,  -286,  -286,
236     -286,  -286,    75,  -286,   414,  -286,   414,   414,  -286,  -286,
237      481,   481,   270,   481,   278,  -286,   288,  -286,   294,   479,
238     -286,  -286,   414,   288,  -286,  -286,   306,  -286,  -286,    11,
239     -286,  -286,  -286,   309,  -286,   288,   307,  -286,  -286,  -286,
240      414,   220,   266,  -286,   158,   288,  -286,  -286,    11,  -286,
241     -286,   308,  -286,  -286,   271,  -286,  -286
242 };
243 
244 /* YYPGOTO[NTERM-NUM].  */
245 static const yytype_int16 yypgoto[] =
246 {
247     -286,  -286,  -286,  -286,  -286,    47,   -10,  -286,  -286,    -6,
248     -286,  -286,   296,   284,   237,   243,   -26,   231,   289,  -137,
249      -12,   221,  -286,  -286,   300,   -57,  -286,  -142,  -286,  -286,
250     -286,   234,  -286,  -286,    59,   190,    21,  -286,   -34,  -227,
251     -221,  -286,  -286,   -15,  -285,   -16,  -286,    66,  -286,  -286,
252     -286,  -286,  -286,  -286,  -286,   227,  -286,  -286,   235,  -286,
253     -286,  -111,   218,   287,  -286,    83,  -286,  -286,  -286,  -286,
254     -286,  -286,  -286,  -107,   132,  -286,   241,  -286,   313,   206,
255     -253,  -279,  -210,   120,   121,  -286,  -286,  -286,  -286,  -286,
256     -286,  -286,  -286,  -286,  -286,  -110,  -286,  -286,    33,  -286,
257     -286,   134,  -286,    35,  -286,  -286,  -286,  -286,    23,  -286,
258     -286,  -286,  -286,  -286,  -286,  -165,  -118,    95,    98,  -200,
259      101,   155,   142,  -286,  -286,  -286,  -286,  -286,  -286,    76,
260     -239,  -234,   157,    -1,    -2,    -5
261 };
262 
263 /* YYTABLE[YYPACT[STATE-NUM]].  What to do in state STATE-NUM.  If
264    positive, shift that token.  If negative, reduce the rule which
265    number is the opposite.  If zero, do what YYDEFACT says.
266    If YYTABLE_NINF, syntax error.  */
267 #define YYTABLE_NINF -182
268 static const yytype_int16 yytable[] =
269 {
270        6,    15,     9,   217,   286,   261,   114,   297,    22,    13,
271      287,   336,   217,   299,   310,    17,    28,   149,    26,    27,
272      235,   190,    34,    31,    56,   205,   348,   350,    31,   212,
273      100,    39,    56,    17,    17,    61,    39,    17,     5,    13,
274      230,    17,   295,    61,    56,     8,    61,   245,    80,     1,
275      345,   112,    17,   304,     5,    61,   268,    12,   370,   190,
276        8,   262,   126,   128,    17,   269,   129,   130,   134,     7,
277      161,   135,   143,   281,   138,   139,     8,   101,    18,    56,
278       56,   222,   270,   266,   336,   355,    56,    64,     8,   269,
279       61,    61,   332,   346,   388,   349,   351,    61,    61,   341,
280       10,   297,   371,    13,   353,   299,   270,    13,   198,   156,
281      199,   159,   160,   381,   271,   112,   402,    14,   106,     8,
282       20,   290,   293,    24,   108,   103,   126,    13,   109,    23,
283      196,    32,   394,   112,    93,    13,   112,    36,   271,   347,
284      217,     5,   112,    94,   221,   112,   324,   126,   228,   231,
285      311,   146,   315,   221,   318,   190,   159,   190,   392,   324,
286       40,   257,   237,   389,   107,   256,    63,    95,   196,   205,
287      264,   286,   285,   212,   367,    64,   400,   404,    57,   127,
288       17,   229,    17,   204,   344,   403,    57,    96,    97,    57,
289      274,   278,    17,   190,   163,   190,   190,   352,    57,   279,
290        8,   276,    13,    67,   280,   202,  -181,  -181,    99,     5,
291      368,   131,   401,   282,    87,   290,   365,   112,   136,   136,
292       89,   140,   272,   377,   324,    90,   324,    68,   126,    68,
293       13,   145,   324,    57,    57,   148,   315,   237,   318,   376,
294       57,    57,   198,  -181,   199,    17,   203,   319,    17,   306,
295      277,  -181,    14,   154,   387,   157,   190,   -40,   307,   362,
296       17,   366,    17,   190,   196,   232,   196,   238,   312,   265,
297      112,   112,   396,   397,     8,   190,   284,   320,   283,    13,
298      302,   221,   159,   330,   112,   190,   333,   300,   -90,   296,
299      272,   303,   305,   334,   165,   159,   322,   335,   331,    20,
300      357,   360,   196,   379,   196,   196,   264,   373,   354,   166,
301      112,   356,   382,   167,   390,     5,   168,   393,   358,   399,
302      395,   126,   363,   361,   406,    35,   405,   204,    78,   142,
303      144,   363,   131,   158,   141,   369,    79,    62,   102,   147,
304      169,   323,   103,   359,   233,   391,   378,   380,   112,   112,
305      329,   112,   165,   170,   171,   162,   214,   112,     5,   159,
306      159,   137,   159,   321,   104,   196,    45,   166,   159,   197,
307      288,   167,   196,     5,   168,   260,   101,    48,    13,   102,
308      216,   107,   133,   103,   196,   308,   309,   374,   301,   398,
309      131,   375,   384,   340,   196,   339,   294,    13,   169,     5,
310       42,   342,     0,   298,    43,   104,     0,    45,     0,   364,
311        0,   170,   171,     0,     0,   105,     0,   106,    48,     0,
312        5,    42,   107,   108,   239,    43,   240,   109,    45,     0,
313       46,   241,     0,     0,     0,   110,     0,     0,     0,    48,
314        0,     5,   289,    49,     0,   239,    42,   240,     0,    45,
315       43,    46,   241,    42,     0,     0,     0,    43,     0,     0,
316       48,     0,     0,     0,    49,     0,     5,    42,     0,     0,
317        0,    43,    44,     5,    45,     0,    46,    47,     0,    44,
318        0,     0,     0,    46,    47,    48,   102,     5,   102,    49,
319      103,   239,   103,   240,     0,     0,    49,    46,   241,     0,
320        0,     0,     0,     0,     0,     0,     5,     0,     5,     0,
321       49,     0,     0,     0,    45,     0,    45,     0,     0,     0,
322        0,   383,     0,    81,     0,    48,     0,    48,    82,   107,
323       83,   107,     0,    84,     0,     0,    85,     0,    86,    87,
324        0,     0,     0,    88,     0,    89,     0,     0,     0,     0,
325       90
326 };
327 
328 static const yytype_int16 yycheck[] =
329 {
330        1,    11,     4,   145,   231,   170,    63,   246,    14,    10,
331      231,   296,   154,   247,   267,     9,    21,     6,    19,    21,
332      157,   131,    28,    24,    36,   136,   305,   306,    29,   136,
333       56,    32,    44,     9,     9,    36,    37,     9,    27,    40,
334       18,     9,   242,    44,    56,    54,    47,   165,    50,    48,
335      303,    63,     9,    62,    27,    56,     5,    10,    16,   169,
336       54,   171,    63,    65,     9,    14,    67,    68,    70,     0,
337      127,    73,    98,    49,    76,    77,    54,     4,    53,    91,
338       92,    53,    31,    18,   369,    53,    98,    40,    54,    14,
339       91,    92,    49,   303,   373,   305,   306,    98,    99,   299,
340       33,   340,    60,   104,    49,   339,    31,   108,    20,   110,
341       22,   112,   114,   366,    63,   127,   395,    30,    45,    54,
342       11,   239,   240,    10,    51,    11,   127,   128,    55,    14,
343      131,    61,   385,   145,     3,   136,   148,    19,    63,   304,
344      282,    27,   154,    12,   145,   157,   283,   148,   149,   151,
345      268,   104,   270,   154,   272,   265,   157,   267,   379,   296,
346       64,   167,   163,   373,    50,   166,    19,    36,   169,   280,
347      171,   398,   229,   280,    18,   128,    18,   398,    36,     8,
348        9,     8,     9,   136,   302,   395,    44,    56,    57,    47,
349      200,     8,     9,   303,     8,   305,   306,   307,    56,    53,
350       54,   202,   203,    23,   206,    23,    17,    18,    58,    27,
351       54,    44,    54,   218,    35,   333,   334,   229,    33,    33,
352       41,    53,    33,   360,   361,    46,   363,    47,   229,    47,
353      231,    31,   369,    91,    92,    40,   354,   238,   356,   357,
354       98,    99,    20,    54,    22,     9,    64,     8,     9,    13,
355      203,    62,    30,    40,   372,    15,   366,    15,   263,     8,
356        9,     8,     9,   373,   265,    18,   267,     8,   269,     8,
357      282,   283,   390,    53,    54,   385,     8,   278,    40,   280,
358        5,   282,   283,   284,   296,   395,   291,    58,    40,    40,
359       33,    59,    13,    15,     6,   296,    40,    53,    18,    11,
360        8,    15,   303,    33,   305,   306,   307,    17,   313,    21,
361      322,   316,    18,    25,     8,    27,    28,     8,   319,    53,
362       13,   322,   327,   325,    53,    29,    18,   280,    44,    92,
363       99,   336,    44,   112,    91,   337,    47,    37,     7,   105,
364       52,   282,    11,   322,   154,   379,   361,   363,   360,   361,
365      284,   363,     6,    65,    66,   128,   138,   369,    27,   360,
366      361,    74,   363,   280,    33,   366,    35,    21,   369,   134,
367      238,    25,   373,    27,    28,   169,     4,    46,   379,     7,
368      139,    50,    69,    11,   385,   265,   265,   354,   254,   391,
369       44,   356,   369,   298,   395,   297,   241,   398,    52,    27,
370        7,   300,    -1,   246,    11,    33,    -1,    35,    -1,   333,
371       -1,    65,    66,    -1,    -1,    43,    -1,    45,    46,    -1,
372       27,     7,    50,    51,    31,    11,    33,    55,    35,    -1,
373       37,    38,    -1,    -1,    -1,    63,    -1,    -1,    -1,    46,
374       -1,    27,    49,    50,    -1,    31,     7,    33,    -1,    35,
375       11,    37,    38,     7,    -1,    -1,    -1,    11,    -1,    -1,
376       46,    -1,    -1,    -1,    50,    -1,    27,     7,    -1,    -1,
377       -1,    11,    33,    27,    35,    -1,    37,    38,    -1,    33,
378       -1,    -1,    -1,    37,    38,    46,     7,    27,     7,    50,
379       11,    31,    11,    33,    -1,    -1,    50,    37,    38,    -1,
380       -1,    -1,    -1,    -1,    -1,    -1,    27,    -1,    27,    -1,
381       50,    -1,    -1,    -1,    35,    -1,    35,    -1,    -1,    -1,
382       -1,    42,    -1,    19,    -1,    46,    -1,    46,    24,    50,
383       26,    50,    -1,    29,    -1,    -1,    32,    -1,    34,    35,
384       -1,    -1,    -1,    39,    -1,    41,    -1,    -1,    -1,    -1,
385       46
386 };
table.h
  1 #define PRIME 211
  2 #define SUBPROC_NUM 100
  3 #define EOS ''
  4 
  5 typedef struct idnode{
  6     char *name;
  7     int type;       /*类型,如int、int*等*/
  8     int offset;
  9     struct idnode *next_hash;       /*指向下一节点的指针*/
 10 }Identifier;
 11 
 12 typedef struct{
 13     char *name;
 14     struct symtable* s;
 15 }subproc;
 16 
 17 typedef struct symtable{
 18     struct symtable* before;
 19     int width;
 20     Identifier *SymbolTable[PRIME];    //哈希表,存放变量
 21     subproc* psubproc_array[SUBPROC_NUM];
 22     int subprocptr;
 23 }symtbl;
 24 
 25 int hashpjw(char *s)
 26 {
 27     char *p;
 28     unsigned h = 0,g;
 29     for(p = s;*p!=EOS;p=p+1)
 30     {
 31         h = (h<<4) + (*p);
 32         if((g = (h & 0xF0000000)))
 33         {
 34             h = h^(g>>24);
 35             h = h^g;
 36         }
 37     }
 38     return h % PRIME;
 39 }
 40 
 41 symtbl *mktable(symtbl *bt)
 42 {
 43     int i;
 44     symtbl* st = (symtbl*)malloc(sizeof(symtbl));
 45     st->before = bt;
 46     st->subprocptr = 0;
 47     for(i = 0;i < PRIME;i++)
 48     {
 49         st->SymbolTable[i] = NULL;
 50     }
 51     return st;
 52 }
 53 
 54 void addwidth(symtbl *st,int offset)
 55 {
 56     st->width = offset;
 57 }
 58 
 59 int enter(symtbl *st,char *name,int type,int offset)
 60 {
 61     int index;
 62     Identifier *entry = (Identifier*)malloc(sizeof(Identifier)),*p,*pb;
 63     entry->name = name;
 64     entry->type = type;
 65     entry->offset = offset;
 66     index = hashpjw(name);
 67 
 68     p = st->SymbolTable[index];
 69 
 70     if(p == NULL||strcmp(p->name,name)>0)
 71     {
 72         entry->next_hash = p;
 73         st->SymbolTable[index] = entry;
 74         return 0;
 75     }
 76 
 77     while(p != NULL)
 78     {
 79         if(strcmp(p->name,name) < 0)
 80         {
 81             pb = p;
 82             p = p->next_hash;
 83         }
 84         else
 85         {
 86             break;
 87         }
 88     }
 89 
 90     if(p == NULL)
 91     {
 92         entry->next_hash = NULL;
 93         pb->next_hash = entry;
 94         return 0;
 95     }
 96     else if(strcmp(p->name,name)>0)
 97     {
 98         entry->next_hash = p;
 99         pb->next_hash = entry;
100         return 0;
101     }
102     else
103     {
104         /*出错处理,重名了*/
105         /*return p->firline;*/
106         return 1;
107     }
108 }
109 
110 void enterproc(symtbl *st,char *name,symtbl *t)     //在st中添加子程序条目
111 {
112     subproc* sproc = (subproc*)malloc(sizeof(subproc));
113     sproc->name = name;
114     sproc->s = t;
115     st->psubproc_array[st->subprocptr] = sproc;
116 }
symboltable.h
  1 (25,0)
  2 (36,SumAverage)
  3 (58,0)
  4 (5,0)
  5 (36,NumberOfIntegers)
  6 (44,0)
  7 (37,3)
  8 (58,0)
  9 (33,0)
 10 (36,A)
 11 (52,0)
 12 (36,B)
 13 (52,0)
 14 (36,C)
 15 (52,0)
 16 (36,D)
 17 (52,0)
 18 (36,E)
 19 (56,0)
 20 (36,integer)
 21 (58,0)
 22 (36,Sum)
 23 (56,0)
 24 (36,integer)
 25 (58,0)
 26 (36,Average)
 27 (52,0)
 28 (36,t)
 29 (56,0)
 30 (36,real)
 31 (58,0)
 32 (3,0)
 33 (36,A)
 34 (57,0)
 35 (37,45)
 36 (58,0)
 37 (36,B)
 38 (57,0)
 39 (37,7)
 40 (58,0)
 41 (36,C)
 42 (57,0)
 43 (37,68)
 44 (58,0)
 45 (36,D)
 46 (57,0)
 47 (37,2)
 48 (58,0)
 49 (36,E)
 50 (57,0)
 51 (37,34)
 52 (58,0)
 53 (36,Sum)
 54 (57,0)
 55 (36,A)
 56 (40,0)
 57 (36,B)
 58 (40,0)
 59 (36,C)
 60 (58,0)
 61 (36,Average)
 62 (57,0)
 63 (36,Sum)
 64 (43,0)
 65 (36,NumberOfIntegers)
 66 (58,0)
 67 (36,t)
 68 (57,0)
 69 (38,1120.000000)
 70 (58,0)
 71 (36,writeln)
 72 (50,0)
 73 (39,'Number of integers = ')
 74 (52,0)
 75 (36,NumberOfIntegers)
 76 (51,0)
 77 (58,0)
 78 (36,writeln)
 79 (50,0)
 80 (39,'Number1 = ')
 81 (52,0)
 82 (36,A)
 83 (51,0)
 84 (58,0)
 85 (36,writeln)
 86 (50,0)
 87 (39,'Number2 = ')
 88 (52,0)
 89 (36,B)
 90 (51,0)
 91 (58,0)
 92 (36,writeln)
 93 (50,0)
 94 (39,'Number3 = ')
 95 (52,0)
 96 (36,C)
 97 (51,0)
 98 (58,0)
 99 (36,writeln)
100 (50,0)
101 (39,'Number4 = ')
102 (52,0)
103 (36,D)
104 (51,0)
105 (58,0)
106 (36,writeln)
107 (50,0)
108 (39,'Number5 = ')
109 (52,0)
110 (36,E)
111 (51,0)
112 (58,0)
113 (36,writeln)
114 (50,0)
115 (39,'Sum = ')
116 (52,0)
117 (36,Sum)
118 (51,0)
119 (58,0)
120 (36,writeln)
121 (50,0)
122 (39,'Average = ')
123 (52,0)
124 (36,Average)
125 (51,0)
126 (10,0)
127 (54,0)
lex.txt

二、支持的产生式(见yacc.y)

  1 %{
  2 /*
  3 * grammar.y
  4 *
  5 * Pascal grammar in Yacc format, based originally on BNF given
  6 * in "Standard Pascal -- User Reference Manual", by Doug Cooper.
  7 * This in turn is the BNF given by the ANSI and ISO Pascal standards,
  8 * and so, is PUBLIC DOMAIN. The grammar is for ISO Level 0 Pascal.
  9 * The grammar has been massaged somewhat to make it LALR, and added
 10 * the following extensions.
 11 *
 12 * constant expressions
 13 * otherwise statement in a case
 14 * productions to correctly match else's with if's
 15 * beginnings of a separate compilation facility
 16 */
 17 
 18 %}
 19 
 20 %token AND ARRAY ASSIGNMENT CASE CHARACTER_STRING COLON COMMA CONST DIGSEQ
 21 %token DIV DO DOT DOTDOT DOWNTO ELSE END EQUAL EXTERNAL FOR FORWARD FUNCTION
 22 %token GE GOTO GT IDENTIFIER IF IN LABEL LBRAC LE LPAREN LT MINUS MOD NIL NOT
 23 %token NOTEQUAL OF OR OTHERWISE PACKED PBEGIN PFILE PLUS PROCEDURE PROGRAM RBRAC
 24 %token REALNUMBER RECORD REPEAT RPAREN SEMICOLON SET SLASH STAR STARSTAR THEN
 25 %token TO TYPE UNTIL UPARROW VAR WHILE WITH
 26 
 27 %%
 28 file : program
 29 ;
 30 
 31 program : program_heading semicolon muldec_m1 block DOT
 32 ;
 33 
 34 muldec_m1 : 
 35 ;
 36 
 37 program_heading : PROGRAM identifier
 38 ;
 39 
 40 identifier_list : identifier_list comma identifier
 41 | identifier
 42 ;
 43 
 44 block : variable_declaration_part
 45 procedure_and_function_declaration_part
 46 statement_part
 47 ;
 48 
 49 constant : non_string
 50 | sign non_string
 51 ;
 52 
 53 sign : PLUS
 54 | MINUS
 55 ;
 56 
 57 non_string : DIGSEQ
 58 ;
 59 
 60 type_denoter : identifier
 61 | new_type
 62 ;
 63 
 64 new_type : new_structured_type
 65 ;
 66 
 67 new_ordinal_type : subrange_type
 68 ;
 69 
 70 subrange_type : constant DOTDOT constant
 71 ;
 72 
 73 new_structured_type : structured_type
 74 ;
 75 
 76 structured_type : array_type
 77 ;
 78 
 79 array_type : ARRAY LBRAC index_list RBRAC OF component_type
 80 ;
 81 
 82 index_list : index_list comma index_type
 83 | index_type
 84 ;
 85 
 86 index_type : ordinal_type ;
 87 
 88 ordinal_type : new_ordinal_type
 89 ;
 90 
 91 component_type : type_denoter ;
 92 
 93 variable_declaration_part : VAR variable_declaration_list semicolon
 94 |
 95 ;
 96 
 97 variable_declaration_list :
 98    variable_declaration_list semicolon variable_declaration
 99 | variable_declaration
100 ;
101 
102 variable_declaration : identifier_list COLON type_denoter
103 ;
104 
105 procedure_and_function_declaration_part :
106   proc_or_func_declaration_list semicolon
107 |
108 ;
109 
110 proc_or_func_declaration_list :
111    proc_or_func_declaration_list semicolon proc_or_func_declaration
112 | proc_or_func_declaration
113 ;
114 
115 proc_or_func_declaration : procedure_declaration
116 ;
117 
118 procedure_declaration : procedure_heading semicolon muldec_m2 procedure_block
119 ;
120 
121 muldec_m2 :
122 ;
123 
124 procedure_heading : procedure_identification
125 | procedure_identification formal_parameter_list
126 ;
127 
128 formal_parameter_list : LPAREN formal_parameter_section_list RPAREN ;
129 
130 formal_parameter_section_list : formal_parameter_section_list semicolon formal_parameter_section
131 | formal_parameter_section
132 ;
133 
134 formal_parameter_section : value_parameter_specification
135 | variable_parameter_specification
136 ;
137 
138 value_parameter_specification : identifier_list COLON identifier
139 ;
140 
141 variable_parameter_specification : VAR identifier_list COLON identifier
142 ;
143 
144 procedure_identification : PROCEDURE identifier ;
145 
146 procedure_block : block ;
147 
148 statement_part : compound_statement ;
149 
150 compound_statement : PBEGIN statement_sequence END ;
151 
152 statement_sequence : statement_sequence semicolon ctrl_m statement
153 | statement
154 ;
155 
156 statement : open_statement
157 | closed_statement
158 ;
159 
160 open_statement : non_labeled_open_statement
161 ;
162 
163 closed_statement : non_labeled_closed_statement
164 ;
165 
166 non_labeled_closed_statement : assignment_statement
167 | procedure_statement
168 | compound_statement
169 | repeat_statement
170 | closed_if_statement
171 | closed_while_statement
172 | closed_for_statement
173 |
174 ;
175 
176 non_labeled_open_statement : open_if_statement
177 | open_while_statement
178 | open_for_statement
179 ;
180 
181 repeat_statement : REPEAT ctrl_m statement_sequence UNTIL repeat_n boolean_expression
182 ;
183 
184 open_while_statement : WHILE ctrl_m boolean_expression DO ctrl_m open_statement
185 ;
186 
187 closed_while_statement : WHILE ctrl_m boolean_expression DO ctrl_m closed_statement
188 ;
189 
190 open_for_statement : FOR control_variable ASSIGNMENT initial_value direction
191    final_value DO for_m open_statement
192 ;
193 
194 closed_for_statement : FOR control_variable ASSIGNMENT initial_value direction
195    final_value DO for_m closed_statement
196 ;
197 
198 open_if_statement : IF boolean_expression THEN ctrl_m statement
199 | IF boolean_expression THEN ctrl_m closed_statement ctrl_n ELSE ctrl_m open_statement
200 ;
201 
202 closed_if_statement : IF boolean_expression THEN ctrl_m closed_statement ctrl_n
203    ELSE ctrl_m closed_statement
204 ;
205 
206 assignment_statement : variable_access ASSIGNMENT expression
207 ;
208 
209 variable_access : identifier
210 | indexed_variable
211 ;
212 
213 indexed_variable :  index_expression_list RBRAC
214 ;
215 
216 index_expression_list : index_expression_list comma index_expression
217 | identifier LBRAC index_expression
218 ;
219 
220 index_expression : expression ;
221 
222 procedure_statement : identifier params
223 | identifier
224 ;
225 
226 params : LPAREN actual_parameter_list RPAREN ;
227 
228 actual_parameter_list : actual_parameter_list comma actual_parameter
229 | actual_parameter
230 ;
231 
232 /*
233 * this forces you to check all this to be sure that only write and
234 * writeln use the 2nd and 3rd forms, you really can't do it easily in
235 * the grammar, especially since write and writeln aren't reserved
236 */
237 actual_parameter : expression
238 ;
239 
240 control_variable : identifier ;
241 
242 initial_value : expression ;
243 
244 direction : TO
245 | DOWNTO
246 ;
247 
248 final_value : expression ;
249 
250 boolean_expression : expression ;
251 
252 expression : simple_expression
253 | simple_expression relop simple_expression
254 ;
255 
256 simple_expression : term
257 | simple_expression addop boolean_m term
258 ;
259 
260 term : factor
261 | term mulop boolean_m factor
262 ;
263 
264 factor : sign factor
265 | exponentiation
266 ;
267 
268 exponentiation : primary
269 ;
270 
271 primary : variable_access
272 | unsigned_constant
273 | LPAREN expression RPAREN
274 | NOT primary
275 ;
276 
277 unsigned_constant : unsigned_number
278 | CHARACTER_STRING
279 ;
280 
281 unsigned_number : unsigned_integer | unsigned_real ;
282 
283 unsigned_integer : DIGSEQ
284 ;
285 
286 unsigned_real : REALNUMBER
287 ;
288 
289 addop: PLUS
290 | MINUS
291 | OR
292 ;
293 
294 mulop : STAR
295 | SLASH
296 | DIV
297 | MOD
298 | AND
299 ;
300 
301 relop : EQUAL
302 | NOTEQUAL
303 | LT
304 | GT
305 | LE
306 | GE
307 ;
308 
309 identifier : IDENTIFIER
310 ;
311 
312 semicolon : SEMICOLON
313 ;
314 
315 comma : COMMA
316 ;
317 
318 boolean_m : 
319 ;
320 
321 ctrl_m:
322 ;
323 
324 ctrl_n:
325 ;
326 
327 repeat_n:
328 ;
329 
330 for_m:
331 ;
yacc.y

三、预测分析表使用bison生成,参考文章《Understanding C parsers generated by GNU Bison》归纳总结https://www.cs.uic.edu/~spopuri/cparser.html

table.h中各表含义如下:

yytranslate[]  建立词法分析器生成的token编号与语法分析器中终结符编号的映射

yytranslante[toke编号] = 语法分析器中此token的终结符编号

特别地,固定yytranslate[0] = 0

Yytname        存放各终结符与非终结符名字,yytname[符号编号]=符号名字,它对语法分析器的

正确性没有什么实质性意义,主要是方便debug时打印符号栈和产生式

yyr1           存放产生式的左部

yyr2           存放产生式右部的长度

yydefact       某状态时的默认规约式(0为出错),yydefact[状态号]=此状态默认使用的产生式号

yydefgoto      非终结符对应的状态转换,yydefgoto[非终结符号]=默认要被压入栈中的状态

yypact         最先被查的表,其值会被加到符号编号上,结果去索引yytable

yypgoto        goto动作时最先被查的表,其值会被加到状态号上,结果去索引yytable

yytable        被索引的表,-1为出错,>0为移进,<0为规约,=0为按yydefact的产生式号规约

yycheck        检查表,每次在查yytable前先使用此表进行检查

使用bison生成的预测好处在于它并不像传统的预测分析表一样存储一个很大的稀疏矩阵,这样做很浪费空间,它生成几个更小的线性一维数组。它生成的表并不是所有的都有用,有用的表其实只有上面介绍的这些,其他表用于打印调试信息和进行错误恢复,比如yytname表。

具体例子如下:

1、移进与规约的选择

状态栈      符号栈      式子

0           #           a……

假设a的编号为5

①yypact[0] = -4 + 5(‘a’) = 1

②yycheck[1]=5? 是③,否④

③按yytable[1]的动作执行

④按yydefact[0]的动作执行

2、goto动作时被压入状态栈的状态确定

假设当前符号栈栈顶为p,状态栈栈顶为10

①yypgoto[p]=2 + 10(state number)=12

②yycheck[12]=10? 是③,否④

③压栈yytable[12]的值

④压栈yydefgoto[p]

四、部分结果截图(总体程序中不会打印此部分)

输出为:状态栈&符号栈(&使用的产生式)

 

原文地址:https://www.cnblogs.com/zhouliyan/p/5941731.html