8/10/2024

Lex in Tiger里

tiger.lex这个文件里面要注意几个点：

  • 怎么处理注释
  • 怎么处理字符串
  • 错误处理机制
  • 文件结束机制
  • 别的有意思的特征对于自己的lexer

Tiger 语言在lex中有下面的几个lexeme：

  1. 保留字（Reserved words） while, for, to, break, let, in, end, function, var, type, array, if, then, else, do, of, nil

  2. 标点符号（Punctuation symbols） , : ; ( ) [ ] { } . + - * / = <> < <= > >= & | :=

  3. 变量名（Identifier） 以字母起手，之后是一连串字母和数字组合

  4. 注释 可以出现在任何两个token之间，从 /* 开始，以*/ 结束，可以嵌套(nested)

  5. 整数常量 只支持非负整数，如果是负的就相当于一个表达式。

  6. String 常量 引号之间的printable character, space, escape sequences（转义串）

语法分析

形式化语言在CS种及其重要，正则语言是最简单的也是应用最广泛的一种，但是有一定的局限性：输入比较长的时候一定会重复的进入某些状态，FA无法记录经过某个状态几次，存储的信息有限（只能记住当前的状态）。计数这种事情在FA中不太可能去做这件事情，因为FA里面是一张表是有限内存，只能数一个事先给定的长度。像要容易匹配的括号对是不能实现的。

解析器的作用：，把词法分析器传来的token串变成语法树

举个例子：

input的token正确性不一定可以保证，所以要先把非法字符串排除，对于合法的构造出parse tree。这里引出了上下文无关语法（CFG‘S）

用上下文无关文法(CFG)来描述语法

Terminal 是需要预先定义的；non—terminal是后来定义的，non-terminal中有一个start symbol；每个production是用来定义non-terminal的，形式就是：上图中的右下方。non-terminal一般使用大写表示，terminal一般用小写表示，start symbol是在第一个production的最左边

praser做的事就是把给定的一串token串构造成一个parse tree。produtction的作用就是不断的利用代替规则（replacement rules），把X出现的地方用Y1….Yn替换掉 (X->Y1…..Yn) 。从start symbol开始不断用替换规则，不断把non-terminal 换成non-terminal 和 terminal 的组合，直到只剩下一串terminal。

举个例：假如有下面左边这幅图的 加和乘的表达式：

在每一步怎么选择合适的production去做替换，这就是语法分析中很重要的事情。我们从start symbol开始用不同的方式去做替换，最后我们替换出sequence of terminal。

从Start symbol开始通过一系列的替换，出现了 一串terminal，这个过程叫做derivation（推导），它也对应了一个parse tree。

在替换过程中选择先替换谁都不是什么问题，但是有可能的两种我们需要额外关注一下。中间的叶子结点在某一步上有很多的non-terminal，一个选择是替换最左边的那个，另一个选择是替换最右边的哪一个。上例中就是最左推导。下图就是最右推导的例子，不断替换最右边的non-terminal。两种情况只是parse tree出现的时间不一样，但最后的结果是一样的。

下面我们来讲一下歧义，一个语法构造完以后，可能会有不同的parse tree。可能最后这些不同的production最后得到的序列是一样的。

左图是最左推导出来的parse tree，左边的加法是先执行的（左结合）。我们也可以像右图一样最右推导，加法就变成右结合了。实际上我们希望的肯定是加法符合左结合。

另外一个就是int * int + int；左图就是先乘后加，而右图就是先加后乘。显然我们希望的是先乘后加，但是在原始输入的时候是没有优先级这个信息的。这就导致了我们用CFG去描述的时候出现了这两种不同的情况。

这种我们就称之为ambiguous，也就是有歧义的语法。

对于某些串来说，出现多个最左推导和最右推导。这个时候就是有歧义的，也就是ill-defined。歧义性的消除需要我们事先的约定，eg:先乘除后加减、加法都是左结合。

我们引入了一个term的东西，T * int而不是T*T就表现了乘法是左结合的。E+T而不是E+E，也能保障加法是左结合的。E和T分开是先有的T再有E，这就保证乘法是有限的。

再举一个歧义的例子：

If-then-else的情况，它可以是只有if-then，也可以都有.

此时的else和哪组if-then就有两种情况了。

我们可以重写这个CFG，要求else匹配最近的then。我们把IF分成两类（一类是if-then-else，另一类是if-then的if）

给定一个语法，我们要用CFG来描述，然后那个工具就会告诉我们是否合法并且工具会构造一个parse tree。剩下的就是写程序比较容易解决的事情。

Top-Down Parsing

递归下降构造parse tree

  1. 从根节点开始（Top）
  2. 从左到右（From left to right）

举个例子理解一下：

一开始E有两个production所以先选第一个；然后向下看，T1可以选3个代替，然后挨个尝试，但是发现3个都无法和后面的匹配，所以回溯E选第二个，然后递归这个过程。

这种我们叫做递归下降法（recursive descent parsing），也就是从根节点开始一个个去试，一旦发现unmatched，就回退（有可能回退多级）。这就是带回溯的递归。要把中间状态记住。这个东西手工实现是比较容易的，但是不是总能很好的工作。

Top-down方法比较害怕的是一个production情况：S->Sa，这样它就会变成死循环，一直在尝试消除S。这种情况我们称之为左递归文法。 不仅仅是S->Sa，还包括通过一系列的推导后，间接地变成这样 S->^+ Sa 也属于左递归文法（left-recursive gramma）;

我们可以消除左递归，也就是要重新写一下这个文法。通常情况下，我们把不属于左递归的拿出来和S’连接，然后S’中放入左递归即可。可以自动地消除左递归。在实际的情况下，有很多的文法是不需要回退的。

Predictive Parsers

parser(解析器可以预测使用哪个production ，通过提前看接下来几个token，来预判），遵循LL(k)的语法。

LL(k)：第一个L代表从左向右扫描；第二个L代表最左递归消除；最后一个k代表，我们往前多看几个k。

我们定义了

begin 
s1;s2;s3;...;sn;
end

定义了token。词法分析就是getToken，拿出下一个扫描到的token。

我们定义一个S函数，也就是我们想看到if / begin/ print作为合法的开头。看到了以后，我们就eat掉，让token前进一格。比如看到if的时候要求中间一定要看到then和else。接着定义L函数和E函数；LL(1)处理statement比较方便，可以通过开头的token推测出整个statement的样子。但是对于expression来说，需要用中缀变后缀的方法，栈上的东西根据操作符的优先级进栈/出栈。但是对于某些例子来说LL(1)不适用，需要提前处理一下，举个例子。

我们定义了右结合的乘法和加法，还有括号表达式。在这个里头我们要消除E的时候，我们没有办法确定是int还是int *，这时候我们就来一个左分解，相当于是提取公因式，我们把E改成TX，公共部分T被提取出来了。这样原本LL(1)只往前看一步解决不了的文法就可以处理了。

LL(1) Parsing Table

左边都是non-terminal，上面是遇到的当前的input。空格代表错误，$就是我们在token串最后加的结束符号。具体每个格里怎么填：应该看图一目了然吧。有了这张表我们就可以查表做parsing了，很简单快速而且不需要回溯，可以用一个自动化工具来做这件事。我们查询[S，a]的产生式，然后就可以把S替换掉。

我们进行一下操作分析：如果栈顶是一个nonterminal，我们拿这个来查表，如果表里有这个东西，我们就用表里的元素来替换这个东西。如果栈顶是一个terminal，如果匹配了，那么next指针就往后移动一个。一直到栈为空或者中间报错。这里要求表上的替换是唯一确定的，如果表里有多个production，那么我们就不知道要选谁了。