概述
读一段程序和读一篇文章的处理是有相似之处的

首先需要能够认出一个个字符（字，单词或者标点）

然后理解文章的结构（段落，句子，句子内部主谓宾等结构）

最后再结合一些前置的知识和上下文，推导、理解每一句的含义，最后理解整个文章的含义
以上就对应了编译的前三个阶段 词法分析 语法分析 语义分析

但是编译的目的是让计算机或者运行环境（而不是人脑）理解程序的含义，所以语义分析的阶段就特别困难，因为人脑可以自然的学习和理解语言，但我们却不知道人脑是怎么做到的。我们只能保证语言的形式可以以语法树的结构来表示和验证，而语义的部分由形式本身来确定。这种由完全由形式确定语义的语言称作形式语言（formal language）,它可以使让机器无歧义地理解程序这一目的变得容易实现。理解形式语言与自然语言的不同能够将编译的研究领域与自然语言识别的领域区分开来。
所以我们最终会由一棵语法树来生成机器能够理解的机器代码，这个过程中会涉及到许多的优化技术，以及底层相关的知识。同时为了保证语言本身的跨平台特性，或者是出于优化的需要和编译器实现的模块化要求，通常会先由语法树生成中间代码，这个过程中进行与平台无关的优化。再由中间代码生成机器相关的代码，中间掺杂进行机器相关的优化。
总结来说，编译器的实现大概以中间代码生成为界分为了前端和后端

整体步骤是：词法分析->语法分析->语义分析（类型检查，中间代码生成和优化）->目标代码生成和优化
因为有像LLVM这样的项目，我们设计一门语言可以只完成编译器的前端，生成某种形式的中间代码，然后和LLVM的后端对接，LLVM可以针对中间代码进行优化，并生成指定机器格式的优化后的机器代码。

当然，这些优化技术本身也有相当的学习价值，基本上可以说是基础库开发的idea来源，因为他们本身就是如何改变程序的结构来达到目的（优化性能，优化表现形式等）的典范。
词法分析与形式系统
为什么讲词法分析会提到正则语言，自动机，形式语言和形式系统这些东西？

这是我上编译原理课的时候最为困惑不解的地方。
事实上形式语言的语法syntax本身就由词法Lexical和语法grammar共同决定，要解析出语法树（syntax tree），两者就不可分割

词法分析的前置是形式语言的字母表，要得出一个token流或符号表

语法分析的前置是推导规则构建的自动机，要得出一棵语法树

前者的输出是后者的输入
一些形式语言的词法本身也是由另一种形式语言定义的，比如C语言的词法中标识符和数字常量的定义可以由正则表达式定义。正则表达式是正则语言的表述工具，它内部实现了自动机。

而用来描述grammar的语言CFG又是另一种形式语言。

所以词法分析和语法分析的本质都是形式语言的推导，或规约。他们的实现就是构建这么一个以字母表和自动机为基础的形式系统。
形式语言与形式系统
由一个字母表按一定规律推导出的一个语言就是形式语言，它的文法就是形式语言的文法

比如由ASCII字母表可以推导出C语言，C是一种形式语言

注意推导是有规则的，因此虽然ASCII字母表也能推导出一部分英语，但是并不是所有的英语都有明确的规则（正如学英语时总会有违反语法的例外场景，事实上就算语法错了根据人也能够理解）而所有正确的C语言程序一定是可以按语法规则规约的

而形式语言的推导类似于初中所做的等式推导题

由一个已知的条件集合和一组规则，经过多步的推导，推出了希望证明的结论

每一步推导都有想要证明的结论，使用的已知条件（比如各种代数规则，交换律结合律之类的），和使用的规则

推导成功就能把结论放入已知条件集合中，作为下一步推导的依据
一个已知条件（形式语言的程序），结论（程序符合语法）加上推导和转化规则（词法/语法规则）构成了形式系统，比如一个编译器的语法解析器（Syntax Parser）

补充：形式语言的意义在于，将语法和语义分割开来。我们可以用多种形式的语法描述同一种语义，比如abbaa， 可以描述为abba*或者ab+a+。这是后期一些优化的理论基础。

正则语言
正则语言是最简单的形式语言

它的字母表有空字符串，普通字符集，代表特殊操作的有并/或（’|’），拼接/且(’’), 重复/闭包(*).

其他的常用扩展有（0或1次（?）,1或更多次（+），指定次数{m,n}，自定义字符集如[^a-z] 等）
推导规则就是匹配运算的自动机（连接，并，闭包这些运算也是匹配)

结论就是匹配成功，或者不成功
上下文无关文法/语法
一个推导中，产生式左边（也就是结论）只有一个非终结符的形式语言文法syntax称为上下文无关文法
只有一个非终结符，就意味着推导到某一步不需要根据前后文（也就是上下文）来确定该用什么规则继续推导。无论这个符号出现在哪里，它的推导方式都是相同的。
终结符就是不可再分的原子token，代表了不可再推导的状态

非终结符是由非终结符和终结符递归构成的，代表了可以继续推导的状态
注意一点 正则文法和上下文无关文法的区别是正则文法无法记忆状态，只能知道当前状态是什么。
正则文法的推导不允许递归，也就是用结论推结论（数学归纳法），而上下文无关文法的非终结符的推导支持递归
不支持递归推导意味着什么？

比如要匹配一些递归嵌套的结构

例如(((i+1) * 2) -7)/2)使用正则文法无法将其识别为一个表达式，还有将类似if …else…的嵌套识别为一个if块都不能用正则文法推导
但是正则语言可以判断操作的数量是否能够被状态数K整数。如果总状态数为2，就是判断操作出现的奇偶性。像是成对出现的标签的匹配是可以用正则表达式去做的，这其中没有用到递归推导，只是识别一个开始和一个对应的结束 ，如果输入本身不满足成对出现，最后一定会匹配不成功。
递归本身和记忆自身状态等价，因此也可以说正则文法没有记忆之前状态的功能。一些正则表达式中有像是可以指定出现次数，还有回溯这样的功能，这其实已经超出了正则语言的范畴。

编译原理中“向前看”的意思
学习编译原理时，在语法分析部分，遇到了一个词“向前看”。比如LL（1）文法，括号中的“1”就是向前看一个输入符号的意思。

比如按顺序输入待分析的串“iloveher”，当前输入的是字符’o’，那么向前看一个字符的意思是看’o’后面的’v’，而不是’o’前一位的’l’！这里的向前，其实是提前的意思，英文原文是’lookahead’，就是提前看的意思，翻译的“向前看”容易产生歧义（我最开始就理解错了，特此记录）。

简介
JavaCC
javaCC 是一个能生成语法和词法分析器的生成程序。语法和词法分析器是字符串处理软件的重要组件。编译器和解释器集成了词法和语法分析器来解释那些含有程序的文件，其中词法和预防分析器被广泛用于各种应用，是用以首先定义用户将要使用的语言，然后用该定义解析相应的条目并且对各种后端数据库制定正确的查询的一种方法。
语法分析
语法分析是编译过程的一个逻辑阶段。语法分析的任务是在词法分析的基础上将单词序列组合成各类语法短语，如“程序”，“语句”，“表达式”等等.语法分析程序判断源程序在结构上是否正确.源程序的结构由上下文无关文法描述.语法分析程序可以用YACC等工具自动生成。
MiniC语法
〈程序〉 → int main() {〈语句块〉* }
〈语句块〉 →〈语句〉| {〈语句块〉* }
〈语句〉 →〈顺序语句〉|〈条件语句〉|〈循环语句〉
〈顺序语句〉→ [〈声明语句〉| 〈赋值语句〉] ”;”
〈声明语句〉→ int ID,ID,…,ID //思考如何表示
〈赋值语句〉→ ID =〈表达式〉
〈条件语句〉→ if〈条件〉〈语句块〉
〈循环语句〉→ while〈条件〉〈语句块〉
〈条件〉 →（〈表达式〉〈关系符〉〈表达式〉）
〈表达式〉 →〈表达式〉〈运算符〉〈表达式〉|（〈表达式〉）|ID|NUM
〈运算符〉 → +|-|*|/
〈关系符〉 → ＜|＜＝|＞|＞＝|＝＝|!=
实现过程
新建一个用于javacc编辑的jjt模板文件：

（1）新建java项目

（2）建立一个语法分析包（例如：package parser）

（3）在parser 包内，“新建”-“其它”-“JavaCC Template File”

（4）创建一个“.jjt”文件
在模板文件中修改词法部分和语法部分，将MiniC的文法依照要求写入jjt文件。
修改jjt文件的main方法，使其执行任务是：指定要进行语法分析s的源程序，执行语法分析，输出语法树。
输出实例
在程序目录下建立main.c文件，用流读取文件，进行分析
int main(){
    int a,b;
    a = 23;
   while(a>2){
       int x;
       x = a+b;     
   }
   return 0;
}


程序连接：https://github.com/BlackJocker1995/Compiler_theory_work02

需求分析

采用至少一种句法分析技术（LL(1)、SLR(1)、LR(1)或LALR(1)）对类高级语言中的基本语句进行句法分析。阐述句法分析系统所要完成的功能。 

（1）能识别以下几类语句：  

     声明语句（包括变量声明、数组声明、记录声明和过程声明） 

     表达式及赋值语句（包括数组元素的引用和赋值） 

     分支语句：if_then_else  

     循环语句：do_while  

     过程调用语句 

（2）自动计算FIRST集和FOLLOW集，自动生成预测分析表 

（3）具备语法错误处理能力，能准确给出错误所在位置，并采用可行的错误恢复策略。 

（4）通过文件导入文法和测试用例，可以通过用户界面显示并编辑测试用例。 

（5）打印输出语法分析器的FIRST集、FOLLOW集和LL(1)分析表（或LR分析表）。另一部分是打印输出语法分析结果。

我选的是LR（1）分析



思路分析





问题思考

关于用文件导入产生式，如何才能在文件中区分终结符和非终结符呢？ 

答：产生式格式如下设计
Start P
P D
P S
S S S
D D D
D proc id ; D S
D T id ;
T X C
T record D
X int
X real
C [ num ] C
C
S id = E ;
S L = E ;
E E + E
E E * E
E - E
E ( E )
E id
E digit
E L
L id [ E ]
L L [ E ]
S if B then S
S if B then S else S
S while B do S
B B || B
B B && B
B ! B
B ( B )
B E < E
B E <= E
B E == E
B E != E
B E > E
B E >= E
S id ( Elist )
Elist Elist , E
Elist E

每一行表示一个产生式，然后非终结符的第一个字母都是大写，终结符的第一个字母小写。每行的第一个单词为产生式左部，其他为产生式右部，这样设计很方便读取。下面是老师给的原文法



要求：给出如下语言成分的文法描述。
   声明语句（包括变量声明、数组声明、记录声明和过程声明）
   表达式及赋值语句（包括数组元素的引用和赋值）
   分支语句：if_then_else 
   循环语句：do_while 
   过程调用语句
/*声明*/
D → D D | proc id ; D S | T id;             
T  → X C |  record D                        
X  → integer | real                 
C  → [num]C | ε                     

/*赋值语句*/
S → id = E ;| L = E ;                   
E → E + E | E * E | -E | (E) | id | digit | L   
L → id[E] | L[E]                        

/*控制流语句*/
S → if B then S1                        
| if B then S1 else S2              
    | while B do S1                 
B → B or B                          
    | B and B                       
    | not B                             
    | (B)                           
    | E relop E                         
    | true                          
    | false                         
relop → < | <= | == | != | > | >=           
/* 过程调用*/
S →call id (Elist)                      
Elist→ Elist, E                     
Elist → E