reduce shift conflict demo
新建一个co.g4
文件
grammar co;
stat:
|expr ';'
|'(' ')' ';'
;
expr: '(' ')'
;
ID: [a-zA-Z]+; // 变量规则
INT: [0-9]+; // 整数规则
新建一个co.g4
文件
grammar co;
stat:
|expr ';'
|'(' ')' ';'
;
expr: '(' ')'
;
ID: [a-zA-Z]+; // 变量规则
INT: [0-9]+; // 整数规则
文法 (Grammar
) 由四部分组成:$(V_f , V_n , P , S)$
$V_f$: 描述的是终结符
$V_n$: 描述的是非终结符
P : 产生式
S : 开始的产生式
right : terminal and notermial left : noterminal procduction: left and right configuration: production whith dot successor: set of configuration
the problem is that how to build the configure set :
the configure set is combine with two set : basic set
and closure set
basic set
:$\lbrace A \rightarrow \omega S.\omega' | A \rightarrow \omega .S\omega' \in P \rbrace$
closure set
:$\lbrace A \rightarrow .\omega | A \rightarrow \omega \in P \quad AND \quad B \rightarrow \phi.A\phi' \in Configure \rbrace$
The basis set consists of all configurations in S having a marker before an s, but with the
marker moved to follow the s;
closure set : {A -> .w | A->w is production}
lr(0)
特别在于状态机:
lr(0) 描述的需要注意以下几个内容:
state
还有一个是$V$ 也就是终结符和非终结符的并集移入-规约冲突
P1
和P2
, P1
右部是产生式P2
右部的前缀规约-规约冲突:
P1
和P2
,P1
右部和P2
右部有公共后缀移入-规约冲突解决: FOLLOW(P)没有交集
规约-规约冲突解决: FIRST(t) 没有交集
S->E
E->E+T | T
T->T*F | F
F->(E) | id
这里
E-> T. (1)
T->T.*F (2)
这两个移入规约冲突
产生式1 是产生式2的前缀
为了解决冲突,我们引入了slr(1),改进了lr(0)的遇到冲突的时候无法解决的问题
计算机语言是什么?
我感觉是一个数学系统
编译成机器码是什么?
是绑定了动作
// lex parse 类型系统 ssa asm elf abi
keyword :
int bool
for while if
比如ssa,是减少死代码,通过常量传播和常量折叠减少运行时的计算
比如sql的逻辑优化: 就是一个逻辑下推 通过变换减少读io
lex : 词法分析
parse: 语法分析构造语法树
cfg优化
codegen
在golang 和php都有ssa 优化,ssa 优化是通过控制流图来做常量传递 常量折叠 和 死代码去除
php的ssa 优化在opcache中,而golang的也在类似的包里面
A program is defined to be in SSA form if each variable is a target of exactly one assignment statement in the program text.
如果程序里面每个变量只被赋值一次那么这个程序就具有ssa 形式
Under SSA form, each variable is defined once. Def-use chains?are data structures that provide, for the single definition of a variable, the set of all its uses. In turn, a use-def chain?, which under SSA consists of a single name, uniquely specifies the definition that reaches the use.
def-use chain 就是输入是 定义(赋值) , 输出是使用被使用的变量的集合
use-def chain 刚好相反 输入是使用的变量 而 输出是他的定义(赋值)的集合, 对于ssa 的程序来说, 每个变量只被赋值(定义)一次,所以这个use-def这个数据结构在ssa形式下这个集合只有一个元素 ssa 形式下
ssa 有什么性质 ?