词法分析和语法分析

1.正则表达式 (Shunting Yard 算法) 后缀正则表达式#

正则表达式：

• 最小单位：∅, ε, a
• 构造方式：选择（A|B） 拼接（AB） 循环（A*）
• 中缀结构

Shunting Yard 算法：

• 从左到右遍历，字符直接输出。
• 遇到运算符压栈。如果新运算符优先级低，输出栈中运算符直到新运算符优先级高于或等于就压栈。
• 括号相当于一个子过程。

后缀正则方便直接遍历来构造NFA，这里通过 Shunting Yard 算法 实现中缀转后缀。

PS：ab 要转换为 a.b，所以要插入连接符 . 。判断条件为 左边 字符 || ) || * 右边 字符 || (。

2.后缀正则表达式 (Thompson构造法) NFA#

Thompson构造法：

• 遍历后缀正则表达式，输入字母则建点，输入运算符则以三种运算构造。处理完加入节点栈中。
• 三种运算构造均满足（一个入口 无入边，一个出口 无出边，即保证不发生倒灌）

3.NFA (子集构造法) DFA#

子集构造法：

• 多个正则构造多个NFA，最后合并如下图所示。这里的NFA1和NFA2表示不同accept状态

        ε → NFA1
start → ε → NFA2
        ε → NFA3

4.DFA (Hopcroft算法) 最小化DFA#

语法分析#

目的：将整个程序转换为语法树

1.LL(1)#

定义：从左到右扫描。自顶向下，最左构造

防止左递归和左公因子的出现，通过构造解决（带来了缺点）

这里要保证每次转移都只有一种情况（带来了局限性）

算法步骤：构造一个栈，弹出初始非终结符，根据第一个token查表，找到对应的句型，将句型右侧从右到左压栈（类似树的前序构造）

2.LR系列#

定义：从左到右扫描。自顶向下，最右构造的逆过程

1) LR(0)#

0含义：规约的时候不看要输入的符号（只要一个状态能规约，就规约）