reduce shift conflict demo
· One min read
新建一个co.g4 文件
grammar co;
stat:
|expr ';'
|'(' ')' ';'
;
expr: '(' ')'
;
ID: [a-zA-Z]+; // 变量规则
INT: [0-9]+; // 整数规则
6 posts tagged with "compile"
View All Tagslr parser
· 3 min read
文法介绍
文法 (Grammar) 由四部分组成:$(V_f , V_n , P , S)$
$V_f$: 描述的是终结符
$V_n$: 描述的是非终结符
P : 产生式
S : 开始的产生式
lr(0)
right : terminal and notermial left : noterminal procduction: left and right configuration: production whith dot successor: set of configuration
build configure set
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) 特别在于状态机：
- reduce state : 转换函数的transition 要么 （一个底部 + 0到1个非终结符）
- read state ： 转换函数的transition 都是终结符
lr(0) 算法
lr(0) 描述的需要注意以下几个内容：
- stack : stack 存了两个内容.一个是
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)的遇到冲突的时候无法解决的问题
SLR(1)
相关阅读
- LR-Parsing of Extended Context Free Grammars
- (Simple LR(k) grammars)[https://dl.acm.org/doi/10.1145/362619.362625]
- https://www.cs.clemson.edu/course/cpsc827/material/LRk/LR1.pdf
- https://blog.csdn.net/m0_37345402/article/details/105678216
- https://blog.csdn.net/qq_33553218/article/details/103522792
- https://blog.csdn.net/qq_35793285/article/details/94378977
- lr0 移入规约冲突
- 其他
- https://blog.csdn.net/m0_37345402/article/details/105678216
llvm
· One min read
a language to machine code
· One min read
计算机语言是什么?
我感觉是一个数学系统
编译成机器码是什么?
是绑定了动作
// lex parse 类型系统 ssa asm elf abi
keyword :
int bool
for while if
ssa optimistic
· 2 min read
优化的本质是什么呢?
比如ssa,是减少死代码,通过常量传播和常量折叠减少运行时的计算
比如sql的逻辑优化: 就是一个逻辑下推 通过变换减少读io
编译的一般步骤:
lex : 词法分析
parse: 语法分析构造语法树
cfg优化
codegen
在golang 和php都有ssa 优化,ssa 优化是通过控制流图来做常量传递 常量折叠 和 死代码去除
php的ssa 优化在opcache中,而golang的也在类似的包里面
structure induction
CFG
construct cfg
ssa
what is ssa
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 形式
def-use chain and use-def chain
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 properties
ssa 有什么性质 ?
DG
JG
insert φ-function
construct ssa
destruct ssa
相关阅读
编译原理
· 2 min read
什么是编译？
一个从一种状态集转换为另外一个状态集的过程
什么是优化？
什么是类型，类型就是集合的约束
一个类型就是一个集合
什么是隐式转换
就是一个集合被编译器材自动从一个集合映射到另外一个集合
因为不同类型的运算是未定义的(也可能是不闭合的,但是更多是未定义的 )
举个例子sql的谓词有些是二值的有些是三值的,导致语义会很难每个人都清楚
同构
什么是同构? 这是我最想弄明白的东西,真的很奇妙
语法和语义(syntax and semantic)
自然语言的语法
如果学过英语,那么i eat apple就是一个主谓宾结构,我对自然语言的语法的理解就是满足某些结构的结构(好吧可能是错误的结论)
数理逻辑的语法
数理逻辑也有相类似的语法
编程语言的语法
编程语言也是特定的token组合就是一个语法结构; 举个例子:
a = 1 ; // 由三个token组成 token<a> token<=> token <1> , 由parse规约而成
语义
操作语义(operate semantic)
描述这个语法对应的操作
表达式(Expressions)
如果是c++的表达式,就是一个序列,这个序列有返回值 举个例子:
The result of the expression always has type void [1]
返回值或者求值结果是void