Stanford Compiler PA2
课程主页：
https://www.edx.org/course/compilers
课程视频：
https://www.bilibili.com/video/BV1NE411376V?p=20&t=6
这次回顾作业2——词法分析。个人感觉这次作业还是很难的，主要是以下几点：
- flex工具的使用——入手需要看一定的资料，并不是半天就能掌握的。
- 正则表达式识别的逻辑——例如注释和字符串的正则表达式应该怎样写才能保证不漏不重。
- Cool编程语言的规则——这部分算是相对简单的，但是入门文档也有30页有余，还是需要花一定时间的。
这次基本是根据大佬的解答才勉强理解的，这里会给出代码的逻辑解释，基本是算是对大佬代码的解析了，主要参考了第一份资料：
其余参考资料：
- https://blog.csdn.net/benladeng29hao/article/details/109111367
- http://dinosaur.compilertools.net/lex/index.html
- https://blog.csdn.net/deepfuture/article/details/83523136
作业分析
准备工作
完成本次作业的整体流程如下：
阅读如下内容：
- PA2。
- cool-manual至少第10章，11章。
- flex介绍：
- cool-parse.h，stringtab.h，stringtab_functions.h
编写cool.flex
下载评分脚本：
wget https://courses.edx.org/assets/courseware/v1/2aa4dec0c84ec3a8d91e0c1d8814452b/asset-v1:StanfordOnline+SOE.YCSCS1+1T2020+type@asset+block/pa1-grading.pl编译：
make lexer测试：
perl pa1-grading.pl
报错处理
如果
make lexer产生如下报错：
/usr/bin/ld: /usr/lib/gcc/x86_64-linux-gnu/9/../../../x86_64-linux-gnu/libfl.so: undefined reference to `yylex' collect2: error: ld returned 1 exit status那么在definitions和rules之间增加如下内容即可：
%option noyywrap参考资料：
https://blog.csdn.net/benladeng29hao/article/details/109111367
几个重要变量
cool_yylval——该变量记录相关信息，这部分使用如下属性：
- error_msg（报错）
- symbol（符号表中变量）
- boolean（布尔变量的值）
相关代码：
extern YYSTYPE cool_yylval;
#if ! defined YYSTYPE && ! defined YYSTYPE_IS_DECLARED
typedef union YYSTYPE
#line 46 "cool.y"
{
Boolean boolean;
Symbol symbol;
Program program;
Class_ class_;
Classes classes;
Feature feature;
Features features;
Formal formal;
Formals formals;
Case case_;
Cases cases;
Expression expression;
Expressions expressions;
char *error_msg;
}三个string table：
- idtable
- inttable
- stringtable
记录标识符，整数，字符串的信息。
流程图
整个词法分析的过程可以用如下流程图概括：
词法分析
所有的说明都在代码中，需要补充的点会加以补充。
注释
/*
* Nested comments
*/
/* 只有不在STRING状态时, 遇到(*才进入BLOCKCOMMENT状态,
commentNum记录嵌套层数, 每次遇到(*则更新。 */
<INITIAL,BLOCKCOMMENT,INLINECOMMENT>"(*" {
commentNum += 1;
BEGIN BLOCKCOMMENT;
};
/* 如果在BLOCKCOMMENT状态遇到*), 则匹配一个(*, 即commentNum减1;
如果commentNum为0, 则说明BLOCKCOMMENT结束, 恢复INITIAL状态。 */
<BLOCKCOMMENT>"*)" {
commentNum -= 1;
if (commentNum == 0){
BEGIN 0;
}
}
/* 如果在非BLOCKCOMMENT状态遇到*), 则直接报错。 */
"*)" {
cool_yylval.error_msg = "Unmatched *)";
return ERROR;
}
/* 换行 */
<BLOCKCOMMENT>"\n" {
curr_lineno++;
};
/* 忽略非\n, (, *字符 */
<BLOCKCOMMENT>[^\n(*]* {};
/* 如果进入该状态, 说明匹配了(或*或)
如果*后续有), 根据规则的出现顺序会匹配*);
如果(后续有*, 根据规则的出现顺序会匹配(*；
其余情形直接忽略。 */
<BLOCKCOMMENT>[(*)] {};
/* 根据4.1, COMMENT中遇到<EOF>直接报错 */
<BLOCKCOMMENT><<EOF>> {
cool_yylval.error_msg = "EOF in comment";
BEGIN 0;
return ERROR;
}
/*
* INLINECOMMENT comments
*/
/* INITIAL状态下进入INLINECOMMENT状态 */
<INITIAL>"--" {
BEGIN INLINECOMMENT;
};
/* 忽略非换行符 */
<INLINECOMMENT>[^\n]* {};
/* 识别换行符 */
<INLINECOMMENT>"\n" {
curr_lineno++;
BEGIN 0;
}整数，标识符和特殊符号
整数
/*
* Integers
*/
{DIGIT}+ {
cool_yylval.symbol = inttable.add_string(yytext);
return INT_CONST;
}标识符
/*
* Identifiers
*/
[A-Z][0-9a-zA-Z_]* {
cool_yylval.symbol = idtable.add_string(yytext);
return TYPEID;
}
[a-z][0-9a-zA-Z_]* {
cool_yylval.symbol = idtable.add_string(yytext);
return OBJECTID;
}特殊符号
特殊符号见cool-manul的第16，17页：
/*
* The multiple-character operators.
*/
"=>" {
return DARROW;
}
"." {
return '.';
}
"@" {
return '@';
}
"~" {
return '~';
}
"*" {
return '*';
}
"/" {
return '/';
}
"+" {
return '+';
}
"-" {
return '-';
}
"<=" {
return LE;
}
"<" {
return '<';
}
"=" {
return '=';
}
"<-" {
return ASSIGN;
}
":" {
return ':';
}
"{" {
return '{';
}
"}" {
return '}';
}
";" {
return ';';
}
"(" {
return '(';
}
")" {
return ')';
}
"," {
return ',';
}字符串
字符串是词法分析中最复杂的部分，这部分要详细讨论。
注意我们的输入是字符串，所以如果输入是转义字符$\text{\c}$，那么得到的结果是$\text{c}$。因此，如果我们希望得到转义字符$\text{\c}$，那么输入应该是$\text{\ \ \ c}$。
根据这点可以将输入分为几类：
- 开始结束符号：$\text{\”}$
- 输出为转义字符的形式：$\text{\ \ \ c}$
- 输入本身即为转义字符：$\text{\c}$
- 其中$\text{\n}$以及$\text{\0}$为非法字符。
- 普通字符。
- $\text{
}$。
整体代码如下：
/*
* String constants (C syntax)
* Escape sequence \c is accepted for all characters c. Except for
* \n \t \b \f, the result is c.
*
*/
/* 只有在INITIAL状态下， 遇到\"才进入STRING状态;
将识别内容存储到yytext */
<INITIAL>\" {
BEGIN STRING;
yymore();
}
/* 识别普通字符 */
<STRING>[^\\\"\n]* {
yymore();
}
/* 转义字符 */
<STRING>\\[^\n] {
yymore();
}
/* 换行 */
<STRING>\\\n {
curr_lineno++;
yymore();
}
/* 涉及到curr_lineno++, 必须直接处理 */
<STRING>\n {
cool_yylval.error_msg = "Unterminated string constant";
curr_lineno++;
BEGIN 0;
return ERROR;
}
/* 结束符直接报错 */
<STRING><<EOF>> {
cool_yylval.error_msg = "EOF in string constant";
BEGIN 0;
yyrestart(yyin);
return ERROR;
}
/* 处理字符串 */
<STRING>\" {
std::string str(yytext, yyleng);
int n = yyleng;
int i = 1;
int j = 0;
char res[n + 1];
//判断是否有\0
for (int j = 1; j < n - 1; j++){
if (str[j] == '\0'){
cool_yylval.error_msg = "String contains null character";
BEGIN 0;
return ERROR;
}
}
while (i < n - 1){
if (str[i] == '\\'){
switch(str[i + 1]){
case 'b':
res[j++] = '\b';
break;
case 't':
res[j++] = '\t';
break;
case 'n':
res[j++] = '\n';
break;
case 'f':
res[j++] = '\f';
break;
default:
res[j++] = str[i + 1];
break;
}
i += 2;
}else{
res[j++] = str[i++];
}
}
if (j >= MAX_STR_CONST){
cool_yylval.error_msg = "String constant too long";
BEGIN 0;
return ERROR;
}
res[j] = '\0';
cool_yylval.symbol = stringtable.add_string((char*)res);
BEGIN 0;
return STR_CONST;
}关键词
这部分很简单的，只要了解
(?i:string)是忽略string的大小写即可。
关键词的列表见cool-parse.h的第115行。
代码如下：
/*
* Keywords are case-insensitive except for the values true and false,
* which must begin with a lower-case letter.
*/
(?i:CLASS) {
return CLASS;
}
(?i:ELSE) {
return ELSE;
}
(?i:FI) {
return FI;
}
(?i:IF) {
return IF;
}
(?i:IN) {
return IN;
}
(?i:INHERITS) {
return INHERITS;
}
(?i:ISVOID) {
return ISVOID;
}
(?i:LET) {
return LET;
}
(?i:LOOP) {
return LOOP;
}
(?i:POOL) {
return POOL;
}
(?i:THEN) {
return THEN;
}
(?i:WHILE) {
return WHILE;
}
(?i:CASE) {
return CASE;
}
(?i:ESAC) {
return ESAC;
}
(?i:NEW) {
return NEW;
}
(?i:OF) {
return OF;
}
(?i:NOT) {
return NOT;
}
t(?i:rue) {
cool_yylval.boolean = 1;
return BOOL_CONST;
}
f(?i:alse) { cool_yylval.boolean = 0;
return BOOL_CONST;
}空格换行
空格换行见cool-manu第16页10.5。
/*
* White space
*/
\n {
curr_lineno++;
}
[ \f\r\t\v]+ {}其他
/*
* else
*/
. {
cool_yylval.error_msg = yytext;
return ERROR;
}本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Doraemonzzz！
相关推荐
评论
ValineLivere