{"tags":["post","创作集"],"title":"一个完整编译器的实现(二) 语法分析","content":"**1 系列说明**\n\n[GitHub地址](https://github.com/DIYgod/Compiler) [各阶段源码](http://www.anotherhome.net/file/compiler/) [各阶段说明集合](http://www.anotherhome.net/1751)\n\n**2 语法分析说明**\n\n语法:组合单词以形成词组 从句 或句子的方法。\n\n经过词法分析,我们已经可以将输入文本识别成一个个的单词,本阶段的目标是将这些单词识别成句子,判断单词的这种组合形式是否符合我们定义的语法。\n\n_2.1 用文法来定义语法_\n\n语法分析需要由递归而获得的额外的表示能力,显然正则表达式已经不能满足我们的需求。\n\n事实上,文法也可以用来描述词法单词的结构,但正则表达式已经可以满足需求,这时使用正则表达式更为简练。\n\n_2.2 LR(1) 分析法_\n\n@%……¥&%#¥太复杂不想说\n\n总之,LR(1) 是一种非常非常强大的分析算法,能够解决很多归约-归约冲突,大多数用上下文无关文法描述其语法的程序设计语言都有一个 LR(1) 文法。\n\n_2.3 使用 Yacc 生成语法分析器_\n\n构造LR(1)分析表的算法简单得足以用计算机来自动完成,而且手工构造十分麻烦无趣,所以使用Yacc是一个明智的决定。\n\n类似Lex,Yacc规范分为三部分\n
%{\n...\n%}\n...\n%%\n...\n第一部分同Lex,包含include和声明\n\n第二部分定义从词法分析中接收的终结符,开始符号,优先级等\n\n第三部分定义文法及语义动作,语法分析阶段只定义文法,语义动作到语义分析时候再完成。\n\n2.3.1 冲突\n\nYacc 选择移近来解决移进-归约冲突,选择使用在文法中先出现的规则来解决归约-归约冲突。\n\n2.3.2 优先级指导\n\n定义优先级是为了解决二义性,这样写文法的时候方便的多。\n\nYacc在第二部分可以假如优先级指导命令\n
%left COMMA\n%right PLUSASSIGN MINUSASSIGN TIMESASSIGN DIVIDEASSIGN ASSIGN\n%left OR\n%left AND\n%left EQ NEQ\n%left LE GE LT GT\n%left PLUS MINUS\n%left TIMES DIVIDE MOD\n%right INC DEC NOT\n%left LPAREN RPAREN LBRACK RBRACK\n自上而下优先级降低,left right 说明单词是左结合还是右结合。\n\n**3 具体实现**\n\n语法分析器和改进过的词法分析器源码见文章开头。\n\n进行到本阶段,编译器发展为四个模块:\n\n1.错误处理模块(errormsg.c errormsg.h):用来产生含文件名和行号的报错信息\n2.常用工具模块(util.c util.h):定义一些常用的函数\n3.词法分析模块(simplec.lex):通过Lex进行词法分析\n4.语法分析模块(simplec.yacc):通过Yacc进行语法分析\n\n其中上一阶段的 token.h 已经不再需要,作为代替,Yacc会根据我们写的文法的单词规范自动生成一个与单词相关的头文件 y.tab.h ;parsetest.c是一个驱动程序,正常情况下会输出 Parsing successful!\n\n附:[ANSI C grammar (Lex)](http://www.lysator.liu.se/c/ANSI-C-grammar-l.html) [ANSI C grammar (Yacc)](http://www.lysator.liu.se/c/ANSI-C-grammar-y.html)\n\n \n\n语法分析 Done.","sources":["xlog"],"attributes":[{"trait_type":"xlog_slug","value":"1764"}],"external_urls":["https://blog.diygod.me/1764"],"date_published":"2015-02-16T21:04:12.000Z"}