ANSI C 的 Lex 和 Yacc

VBProFan

篇幅有限，只贴个 AnsiC.L 出来吧，因为我打算准备用 VB6 写一个 ANSI C 的词法分析器，贴出来有助于我查找它的词汇表。

1. 
   
2. D   [0-9]
   
3. L   [a-zA-Z_]
   
4. H   [a-fA-F0-9]
   
5. E   [Ee][+-]?{D}+
   
6. P                       [Pp][+-]?{D}+
   
7. FS   (f|F|l|L)
   
8. IS                      ((u|U)|(u|U)?(l|L|ll|LL)|(l|L|ll|LL)(u|U))
   
9. %{
   
10. #include <stdio.h>
    
11. #include "y.tab.h"
    
12. void count(void);
    
13. %}
    
14. %%
    
15. "/*"   { comment(); }
    
16. "//"[^\n]*              { /* consume //-comment */ }
    
17. 
    
18. "auto"   { count(); return(AUTO); }
    
19. "_Bool"   { count(); return(BOOL); }
    
20. "break"   { count(); return(BREAK); }
    
21. "case"   { count(); return(CASE); }
    
22. "char"   { count(); return(CHAR); }
    
23. "_Complex"  { count(); return(COMPLEX); }
    
24. "const"   { count(); return(CONST); }
    
25. "continue"  { count(); return(CONTINUE); }
    
26. "default"  { count(); return(DEFAULT); }
    
27. "do"   { count(); return(DO); }
    
28. "double"  { count(); return(DOUBLE); }
    
29. "else"   { count(); return(ELSE); }
    
30. "enum"   { count(); return(ENUM); }
    
31. "extern"  { count(); return(EXTERN); }
    
32. "float"   { count(); return(FLOAT); }
    
33. "for"   { count(); return(FOR); }
    
34. "goto"   { count(); return(GOTO); }
    
35. "if"   { count(); return(IF); }
    
36. "_Imaginary"  { count(); return(IMAGINARY); }
    
37. "inline"  { count(); return(INLINE); }
    
38. "int"   { count(); return(INT); }
    
39. "long"   { count(); return(LONG); }
    
40. "register"  { count(); return(REGISTER); }
    
41. "restrict"  { count(); return(RESTRICT); }
    
42. "return"  { count(); return(RETURN); }
    
43. "short"   { count(); return(SHORT); }
    
44. "signed"  { count(); return(SIGNED); }
    
45. "sizeof"  { count(); return(SIZEOF); }
    
46. "static"  { count(); return(STATIC); }
    
47. "struct"  { count(); return(STRUCT); }
    
48. "switch"  { count(); return(SWITCH); }
    
49. "typedef"  { count(); return(TYPEDEF); }
    
50. "union"   { count(); return(UNION); }
    
51. "unsigned"  { count(); return(UNSIGNED); }
    
52. "void"   { count(); return(VOID); }
    
53. "volatile"  { count(); return(VOLATILE); }
    
54. "while"   { count(); return(WHILE); }
    
55. {L}({L}|{D})*  { count(); return(check_type()); }
    
56. 0[xX]{H}+{IS}?  { count(); return(CONSTANT); }
    
57. 0{D}+{IS}?  { count(); return(CONSTANT); }
    
58. {D}+{IS}?  { count(); return(CONSTANT); }
    
59. L?'(\\.|[^\\'\n])+' { count(); return(CONSTANT); }
    
60. {D}+{E}{FS}?  { count(); return(CONSTANT); }
    
61. {D}*"."{D}+({E})?{FS}? { count(); return(CONSTANT); }
    
62. {D}+"."{D}*({E})?{FS}? { count(); return(CONSTANT); }
    
63. 0[xX]{H}+{P}{FS}?               { count(); return(CONSTANT); }
    
64. 0[xX]{H}*"."{H}+({P})?{FS}?     { count(); return(CONSTANT); }
    
65. 0[xX]{H}+"."{H}*({P})?{FS}?     { count(); return(CONSTANT); }
    
66. 
    
67. L?"(\\.|[^\"\n])*" { count(); return(STRING_LITERAL); }
    
68. "..."   { count(); return(ELLIPSIS); }
    
69. ">>="   { count(); return(RIGHT_ASSIGN); }
    
70. "<<="   { count(); return(LEFT_ASSIGN); }
    
71. "+="   { count(); return(ADD_ASSIGN); }
    
72. "-="   { count(); return(SUB_ASSIGN); }
    
73. "*="   { count(); return(MUL_ASSIGN); }
    
74. "/="   { count(); return(DIV_ASSIGN); }
    
75. "%="   { count(); return(MOD_ASSIGN); }
    
76. "&="   { count(); return(AND_ASSIGN); }
    
77. "^="   { count(); return(XOR_ASSIGN); }
    
78. "|="   { count(); return(OR_ASSIGN); }
    
79. ">>"   { count(); return(RIGHT_OP); }
    
80. "<<"   { count(); return(LEFT_OP); }
    
81. "++"   { count(); return(INC_OP); }
    
82. "--"   { count(); return(DEC_OP); }
    
83. "->"   { count(); return(PTR_OP); }
    
84. "&&"   { count(); return(AND_OP); }
    
85. "||"   { count(); return(OR_OP); }
    
86. "<="   { count(); return(LE_OP); }
    
87. ">="   { count(); return(GE_OP); }
    
88. "=="   { count(); return(EQ_OP); }
    
89. "!="   { count(); return(NE_OP); }
    
90. ";"   { count(); return(';'); }
    
91. ("{"|"<%")  { count(); return('{'); }
    
92. ("}"|"%>")  { count(); return('}'); }
    
93. ","   { count(); return(','); }
    
94. ":"   { count(); return(':'); }
    
95. "="   { count(); return('='); }
    
96. "("   { count(); return('('); }
    
97. ")"   { count(); return(')'); }
    
98. ("["|"<:")  { count(); return('['); }
    
99. ("]"|":>")  { count(); return(']'); }
    
100. "."   { count(); return('.'); }
     
101. "&"   { count(); return('&'); }
     
102. "!"   { count(); return('!'); }
     
103. "~"   { count(); return('~'); }
     
104. "-"   { count(); return('-'); }
     
105. "+"   { count(); return('+'); }
     
106. "*"   { count(); return('*'); }
     
107. "/"   { count(); return('/'); }
     
108. "%"   { count(); return('%'); }
     
109. "<"   { count(); return('<'); }
     
110. ">"   { count(); return('>'); }
     
111. "^"   { count(); return('^'); }
     
112. "|"   { count(); return('|'); }
     
113. "?"   { count(); return('?'); }
     
114. [ \t\v\n\f]  { count(); }
     
115. .   { /* Add code to complain about unmatched characters */ }
     
116. %%
     
117. int yywrap(void)
     
118. {
     
119. return 1;
     
120. }
     
121. 
     
122. void comment(void)
     
123. {
     
124. char c, prev = 0;
     
125.   
     
126. while ((c = input()) != 0)      /* (EOF maps to 0) */
     
127. {
     
128.   if (c == '/' && prev == '*')
     
129.    return;
     
130.   prev = c;
     
131. }
     
132. error("unterminated comment");
     
133. }
     
134. 
     
135. int column = 0;
     
136. void count(void)
     
137. {
     
138. int i;
     
139. for (i = 0; yytext != '\0'; i++)
     
140.   if (yytext == '\n')
     
141.    column = 0;
     
142.   else if (yytext == '\t')
     
143.    column += 8 - (column % 8);
     
144.   else
     
145.    column++;
     
146. ECHO;
     
147. }
     
148. 
     
149. int check_type(void)
     
150. {
     
151. /*
     
152. * pseudo code --- this is what it should check
     
153. *
     
154. * if (yytext == type_name)
     
155. *  return TYPE_NAME;
     
156. *
     
157. * return IDENTIFIER;
     
158. */
     
159. /*
     
160. * it actually will only return IDENTIFIER
     
161. */
     
162. return IDENTIFIER;
     
163. }
     

复制代码

lex 和 yacc 的 Ansi C.rar (22.88 KB, 下载次数: 610)

2010-8-25 00:46 上传

点击文件名下载附件
内含：

AnsiC.L
AnsiC.Y
AnsiC_Lex.h
AnsiC_Lex.c
AnsiC.v
AnsiC_Yacc.c
AnsiC_Yacc.h

那些 .c, .h 文件是我用一个未注册的工具编译的，.L, .Y则我是在网页上复制，粘贴进文本文件得到的。

PS：为了区别 Lex 和 Yacc 生成的 c h 文件，我改了它们的文件名，但忘记修改了里面的内容，所以不能直接编译，注意一下啦~

VBProFan

有个问题请教一下大家，像：
“#include<stdlib.h>”
这种情况怎么办？

1. 假如把“<”看做一个单独的词，那么 stdlib . h > 就是四个单独的词了，如果这个头文件名里面有特殊字符，如空格、句点、等号等等，那就明显不对了，文件名就应该是一个词而已，却被分开了；

2. 假如把“<”看做字符串起始符号，“>”看做字符串的终止符号，那么遇到 a + b < c 这种有大于号的情况时又不对了；

3. 根据前面是否有 include 来区分“<”是左尖括号还是小于号，但这好像又是语法分析，不属于词法分析的范畴了。

上面的 Lex 的程序似乎也没有考虑到这种情况。

acme_pjz

呵呵，我原本打算用VB6实现山寨Lex和YACC……前一个基本实现了，后一个没实现……

至于你2楼的问题，预处理器把#开头的语句全部砍掉了……

download

#include<stdlib.h>
好像是把stdlib.h的内容直接插到这个位置，然后再处理

VBProFan

呵呵，我原本打算用VB6实现山寨Lex和YACC……前一个基本实现了，后一个没实现……

至于你2楼的问题，预处理器把#开头的语句全部砍掉了……
acme_pjz 发表于 2010-8-25 20:39

这么牛叉？Lex 做出来了？怎么不放出来让我们玩玩呢？
Yacc 做不出来可以做个容易一点的吧。像通过构造 First 和 Follow 集合得到 LL(1)分析器貌似还是比较简单的。
原来预处理器并非用词法和语法分析的技术（有限自动机和下推自动机），估计是用一些高级字符串处理函数，就像我以前搞的一些山寨的词法语法分析程序一样 （例如语法高亮的汇编开发环境、C Func 转 VB、VB Prolog 解释器……）

VBProFan

#include
好像是把stdlib.h的内容直接插到这个位置，然后再处理
download 发表于 2010-8-25 20:53

这个地球人都知道，不过我到现在还没想明白，如果出现语法错误（分h文件和c文件两种情况），要定位时就复杂了。如果你用h文件的字符串来替换到这里，在c中出现语法错误，你显示的只能是在c中的行数，但对 LR 分析器来说，它分析的是替换后的字符串……

难道在内存中保存两份字符串，一份是替换前的c的，一份是替换后的c的？

download

估计是先分析h，有错就报错，没错就合并到c
头文件出错VC好像是直接报h的行号。这种情况还是比较容易，
CPP的那个模板才复杂，调试也很可怕，幸好VC支持的比较好。

acme_pjz

6# VBProFan

不是，只生成一个合并后的文件，不过里面可能有#file或#line等关键字，在词法分析程序读到的时候就更新文件名和行号信息……

VBProFan

发现一个好东西：

http://blog.csdn.net/huyansoft/archive/2008/05/26/2484297.aspx
C/C++预处理 ISO/ANSI C标准译文与注解

VBProFan

在看语法分析的文法定义部分时，我就在想：C的文法应该如何定义呢？太复杂了，怎么想都想不出，回来再一看 Ansi C 的 Yacc 源码，恍然大悟，真是太经典了，忍不住发几条上来：

jump_statement
: GOTO IDENTIFIER ';'
| CONTINUE ';'
| BREAK ';'
| RETURN ';'
| RETURN expression ';'
;

这是对跳转语句的总结，表面上看上去很不同的 goto 和 return，居然是一起处理的，到现在还想不出为什么，汇编不是也有子程序和return语句吗？难道C的return也翻译为jnz之类的？。而continue和break一开始看上去时反应不过来，想想后确实也是翻译为jnz之类的。

external_declaration
: function_definition
| declaration
;

这个基本上接近开始符号了，C程序就是由全局声明和函数定义组成的。

iteration_statement
: WHILE '(' expression ')' statement
| DO statement WHILE '(' expression ')' ';'
| FOR '(' expression_statement expression_statement ')' statement
| FOR '(' expression_statement expression_statement expression ')' statement
| FOR '(' declaration expression_statement ')' statement
| FOR '(' declaration expression_statement expression ')' statement
;

对循环语句的总结，呵呵。

selection_statement
: IF '(' expression ')' statement
| IF '(' expression ')' statement ELSE statement
| SWITCH '(' expression ')' statement
;

对分支语句的总结，呵呵。

expression_statement
: ';'
| expression ';'
;

语句组可以是空语句，也可以是语句序列，最简单的左递归定义。

statement
: labeled_statement
| compound_statement
| expression_statement
| selection_statement
| iteration_statement
| jump_statement
;

这个也很经典，语句的类型。

几乎全是经典啊~ 我要翻译、整理、打印出来膜拜和诵读。整个 C 的语法仅400多行就可以全部精确的描述，真是太神奇了！