英语句子改错?语法分析器的输出?自制编译器：语法分析器（二）

你是否正在寻找关于语法分析器的内容？让我把最受欢迎的东西奉献给你：

这篇博文拖了好久才写完，其一是语法分析器本身的难度实在有点超出我的预料，以至于反复重构多次才完成，其二是因为弄了个xbox玩，占用了一部分的课余时间= =！。

本篇博文将分为以下几个部分来描述一下语法分析器的具体实现，理论、部分典型节点与结果。

一、语法制导翻译、LL与LL（X）语法、左递归等其它

为什么要写一个语法分析器？语法分析器的作用不仅仅是来检查词素列表中的序列是否是一个我们语言的语句，更重要的是只有借助语法分析器得到的抽象语法树，才能够生成中间代码或者具体的目标代码，这个过程叫做语法制导翻译（syntax-directed translation）。在紫龙书（编译原理第二版）的封面上，一个拿盾的骑士正在和一个喷火龙决斗，其中龙的身上写的是Complexity of Complier Design，而骑士的盾上写的则是Syntax Directed Translation，因此把语法制导翻译当作是编译器前端的核心也不为过。

展开语法树的过程实质上也就是将词素不断地对应到我们语言定义的递推式的过程，换个说法其实也就是不断地展开语言的递推式，使之符合已有词素的过程。这个展开的过程从方法上来讲可分为两种：LL和LR。其中第一个字母代表从左到右读词素序列，第二个字母L代表尝试最先展开最左边的非终结符号，R代表尝试从右边开始将词素归约为非终结符好。换言之，LL是一种自顶向下的展开方法，LR是一种自底向上的归约方法，本文采用的技术为LL，所以以下也以讨论LL为主。

为了使编译器能高效迅速，一个良好的语法设计必须是一个LL（1）语法，什么是LL（1）语法呢？举个例子，当我们面对如下推导式的时候：

ids-> id| ----------1

id.ids| -----------2

ids[expr] | -----------3

this

此时我们读到了一个词素id，是展开成1、2、3中的哪种呢？当然目前我们无法判断，因此需要多读入下一个词素才能进行判断。如果读到的是[，则展开成3。如果读到了.则展开成2，否则展开成1。但问题是有些情况下，多读入一个词素或许还不能进行判断，当一个语言的语法中，只要多读入X个词素就能唯一的确定推导式，则称其为LL（X）文法。很遗憾，我们的语法不是LL（1）语法，虽然有很多推导式的处理技巧可以将一个非LL（1）的语法处理成LL（1）的语法，但这样会失去语法的直观性。考虑再三我在“不是很合理但易于理解的语法” 和 “合理高效的不直观的语法”之间选择了前者。

因此既然我们的语法并非LL（1）的，因此在语法分析的过程中，我们只是不断的去尝试展开，如果不成功，则回溯，。虽然这是比较低效的，但文法中的大多数推导式并不复杂，所以处理的时间完全可以接受。

考虑如下 推导式：

expr --> (expr) ------------1

ids| ------------2

number| -----------3

literal| ------------4

func-call| ------------5

expr opsexpr|

这个推导式不满足LL（1），假设当前读到了一个id，目前可供选择的有2、4、5，然后又读入了一个“。”，目前可供选择的还是2、4、5，又读入了一个id，可供选择的还是2、4、5，然后读入了一个“（” ，这时候才能确定唯一的展开式func-call。但这个表达式除了不满足LL（1）之外还有其它的问题：左递归。

假设expr上来就尝试去展开成5的形式，因为是递归展开的过程，5中最左边的expr又会尝试展开成5的形式，然后这个过程就不断递归下去最终导致stack overflow。虽然有很多方法和技巧可以改变推导式的形式来消除左递归，但是依然本着易于理解的原则，我们在语法分析中通过使用朴素的笨办法来避免这种情况的发生。所谓的笨办法就是：

（1）按优先级先展开1234，然后都失败再展开成5。

（2）设置最大展开深度为200，超过了直接报错。

虽然很笨很低效，但勉强够用了。

二、语法分析器结构

语法分析器在实现上分以下几个部分，第一部分为SyntaxTreeGenerator，负责读入词素，和词法分析器以及后端程序进行交流，算是语法分析器的对外接口。其次使用GlobalVars来存储各种全局数据，记录分析过程中的各种信息。最后就是各种节点，每个节点在分析的过程中若需要其它信息则通过GlobalVars来解耦。接下来通过几个例子来具体说明这些节点是如何展开语法分析的：

（1）id

本文来自电脑杂谈，转载请注明本文网址：
https://www.pc-fly.com/a/ruanjian/article-21226-1.html