- 浏览: 3013736 次
- 性别:
- 来自: 海外
文章分类
- 全部博客 (430)
- Programming Languages (23)
- Compiler (20)
- Virtual Machine (57)
- Garbage Collection (4)
- HotSpot VM (26)
- Mono (2)
- SSCLI Rotor (1)
- Harmony (0)
- DLR (19)
- Ruby (28)
- C# (38)
- F# (3)
- Haskell (0)
- Scheme (1)
- Regular Expression (5)
- Python (4)
- ECMAScript (2)
- JavaScript (18)
- ActionScript (7)
- Squirrel (2)
- C (6)
- C++ (10)
- D (2)
- .NET (13)
- Java (86)
- Scala (1)
- Groovy (3)
- Optimization (6)
- Data Structure and Algorithm (3)
- Books (4)
- WPF (1)
- Game Engines (7)
- 吉里吉里 (12)
- UML (1)
- Reverse Engineering (11)
- NSIS (4)
- Utilities (3)
- Design Patterns (1)
- Visual Studio (9)
- Windows 7 (3)
- x86 Assembler (1)
- Android (2)
- School Assignment / Test (6)
- Anti-virus (1)
- REST (1)
- Profiling (1)
- misc (39)
- NetOA (12)
- rant (6)
- anime (5)
- Links (12)
- CLR (7)
- GC (1)
- OpenJDK (2)
- JVM (4)
- KVM (0)
- Rhino (1)
- LINQ (2)
- JScript (0)
- Nashorn (0)
- Dalvik (1)
- DTrace (0)
- LLVM (0)
- MSIL (0)
最新评论
-
mldxs:
虽然很多还是看不懂,写的很好!
虚拟机随谈(一):解释器,树遍历解释器,基于栈与基于寄存器,大杂烩 -
HanyuKing:
Java的多维数组 -
funnyone:
Java 8的default method与method resolution -
ljs_nogard:
Xamarin workbook - .Net Core 中不 ...
LINQ的恶搞…… -
txm119161336:
allocatestlye1 顺序为 // Fields o ...
最近做的两次Java/JVM分享的概要
看到phyeas同学在试写JavaScript语法,顺便参一腿 =v=
本文里的代码放在附件里了,有需要的拿。
关于语法中左递归/右递归与规则的左结合/右结合的关系,我觉得就照着简单的表达式语法把推导过程画出来,找找感觉就能行。要注意的是推导结束后,把每步推导过程画成树(也就是解析树或者叫语法树),离根越远的节点在就越先被求值,也就是“优先级高”的表现了。写这帖的时候懒得画例子了……有必要再补充。
自顶向下的解析方法,如递归下降式或者LL式,一般无法支持左递归的语法,无聊是直接左递归还是间接左递归。这是因为它总是从推导规则中的第一个符号开始推,如果第一个符号就是自己或者间接回回到自己,那么解析过程就无法前进,就无限递归而出错了。(近年来有人提出过一些改进方案使自顶向下解析可以支持左递归,这帖里就不讨论了。有兴趣的同学可以阅读这篇论文:Packrat parsers can support left recursion)。
传统上,为了解决无法左递归的问题,可以改写语法规则,通过引入一个ε转换来把左递归变为右递归。但是这样得到的语法树的结合性就不对了,要得到正确的语法树需要做额外的工作来把树的形状转换回来。
LR系的解析方式则既支持左递归也支持右递归,写起语法来就轻松很多。结合性直接靠语法的递归位置就可以表达。
结合性有两个经典的应用场景,一是表达式的解析,二是if-else问题的解决。这帖主要着眼于前者。
表达式的形式比较固定,但传统上运算符有不同优先级,写语法的时候为了照顾优先级可以选择把相似的结构重复写在多个规则里,让这些规则的层次表达优先级的差别。但规则多了,状态图也就变复杂了。
通过显式指定运算符的优先级,语法中结构相似的规则可以写在同一条规则里,既简化了语法,对应的解析器的效率也更高。
GNU Bison是主要采用LALR(1)的解析器生成器。它支持显式指定规则的优先级以及结合性。
那么优先级能否跨规则而存在呢?先看个例子:
calc1.y
这是个简单的计算器,支持加、减、乘、除、负、幂等运算,并且可以通过括号改变表达式的结合性。注意到,所有表示“表达式”的规则都在同一个大规则expr里,它们的结合性和优先级则在语法文件的头部声明。
如果把expr改为下面的样子呢?
calc2.y
bison会抱怨说出现了5个递进/规约冲突。用bison -v calc2.y命令,查看calc2.output,可以看到冲突出现在状态17:
在这个状态时,下一个字符假如是+,那么既可以递进并转到状态10,也可以规约,于是就冲突了。
问题的关键就在于,这个“优先级”到底是干嘛用的。以calc1.y为例,如果没有指定运算符优先级,匹配到这样一个状态:
(“.”表示当前匹配的位置)
假如下一个符号是*,那么到底应该选择递进,变为:
还是规约,变为:
呢?
有了优先级,bison就可以比较递进与规约的选择间涉及的优先级;看到*的优先级比+高,于是选择递进。
而在calc2.y中,加减乘除幂这几个带优先级的运算符堆在了binop规则中。匹配该规则其实不需要优先级,单靠lookahead就足够了;在遇到加减乘数幂这几个运算符时,bison肯定会选择规约为binop;规约后,binop本身就不带有任何优先级信息了。而在expr规则中,需要优先级去区分递进或规约的expr binop expr子规则却得不到任何优先级信息,于是递进/规约冲突又冒出来了。
phyeas的问题:
答案是:不会。
进一步阅读:
首推自然是bison的手册。
这个帖子也可以读读,也是用表达式计算器为例子来讲解的。现在好困,不想码那么多字,既然有现成的解释我也就不用码了 =v=
本文里的代码放在附件里了,有需要的拿。
关于语法中左递归/右递归与规则的左结合/右结合的关系,我觉得就照着简单的表达式语法把推导过程画出来,找找感觉就能行。要注意的是推导结束后,把每步推导过程画成树(也就是解析树或者叫语法树),离根越远的节点在就越先被求值,也就是“优先级高”的表现了。写这帖的时候懒得画例子了……有必要再补充。
自顶向下的解析方法,如递归下降式或者LL式,一般无法支持左递归的语法,无聊是直接左递归还是间接左递归。这是因为它总是从推导规则中的第一个符号开始推,如果第一个符号就是自己或者间接回回到自己,那么解析过程就无法前进,就无限递归而出错了。(近年来有人提出过一些改进方案使自顶向下解析可以支持左递归,这帖里就不讨论了。有兴趣的同学可以阅读这篇论文:Packrat parsers can support left recursion)。
传统上,为了解决无法左递归的问题,可以改写语法规则,通过引入一个ε转换来把左递归变为右递归。但是这样得到的语法树的结合性就不对了,要得到正确的语法树需要做额外的工作来把树的形状转换回来。
LR系的解析方式则既支持左递归也支持右递归,写起语法来就轻松很多。结合性直接靠语法的递归位置就可以表达。
结合性有两个经典的应用场景,一是表达式的解析,二是if-else问题的解决。这帖主要着眼于前者。
表达式的形式比较固定,但传统上运算符有不同优先级,写语法的时候为了照顾优先级可以选择把相似的结构重复写在多个规则里,让这些规则的层次表达优先级的差别。但规则多了,状态图也就变复杂了。
通过显式指定运算符的优先级,语法中结构相似的规则可以写在同一条规则里,既简化了语法,对应的解析器的效率也更高。
GNU Bison是主要采用LALR(1)的解析器生成器。它支持显式指定规则的优先级以及结合性。
那么优先级能否跨规则而存在呢?先看个例子:
calc1.y
%{ #include <stdio.h> #include <ctype.h> #include <math.h> %} %union { double dval; } %token <dval> NUMBER %token POW %left '+' '-' %left '*' '/' %nonassoc UMINUS %right POW %type <dval> expr %% line : expr '\n' { printf("%lf\n", $1); } ; expr : NUMBER { $$ = $1; } | expr '+' expr { $$ = $1 + $3; } | expr '-' expr { $$ = $1 - $3; } | expr '*' expr { $$ = $1 * $3; } | expr '/' expr { if (0 == $3) yyerror("divided by zero"); else $$ = $1 / $3; } | '-' expr %prec UMINUS { $$ = -$2; } | expr POW expr { $$ = pow($1, $3); } | '(' expr ')' { $$ = $2; } ; %% int main() { return yyparse(); } int yyerror(char* s) { fprintf(stderr, "%s\n", s); return 1; } int end = 0; int yylex() { if (end) return 0; int c; /* skip space */ while (' ' == (c = getchar())) { } if (isdigit(c)) { ungetc(c, stdin); scanf("%lf", &yylval); return NUMBER; } if ('*' == c) { c = getchar(); if ('*' == c) { return POW; } else { ungetc(c, stdin); return '*'; } } if ('\n' == c) { end = 1; } return c; }
这是个简单的计算器,支持加、减、乘、除、负、幂等运算,并且可以通过括号改变表达式的结合性。注意到,所有表示“表达式”的规则都在同一个大规则expr里,它们的结合性和优先级则在语法文件的头部声明。
如果把expr改为下面的样子呢?
calc2.y
expr : NUMBER { $$ = $1; } | expr binop expr { switch ($2) { case '+': $$ = $1 + $3; break; case '-': $$ = $1 - $3; break; case '*': $$ = $1 * $3; break; case '/': $$ = $1 / $3; break; case POW: $$ = pow($1, $3); break; } } | '-' expr { $$ = -$2; } | '(' expr ')' { $$ = $2; } ; binop : '+'| '-' | '*' | '/' | POW ;
bison会抱怨说出现了5个递进/规约冲突。用bison -v calc2.y命令,查看calc2.output,可以看到冲突出现在状态17:
state 17 3 expr: expr . binop expr 3 | expr binop expr . POW shift, and go to state 9 '+' shift, and go to state 10 '-' shift, and go to state 11 '*' shift, and go to state 12 '/' shift, and go to state 13 POW [reduce using rule 3 (expr)] '+' [reduce using rule 3 (expr)] '-' [reduce using rule 3 (expr)] '*' [reduce using rule 3 (expr)] '/' [reduce using rule 3 (expr)] $default reduce using rule 3 (expr) binop go to state 15
在这个状态时,下一个字符假如是+,那么既可以递进并转到状态10,也可以规约,于是就冲突了。
问题的关键就在于,这个“优先级”到底是干嘛用的。以calc1.y为例,如果没有指定运算符优先级,匹配到这样一个状态:
expr '+' expr .
(“.”表示当前匹配的位置)
假如下一个符号是*,那么到底应该选择递进,变为:
expr '+' expr '*' .
还是规约,变为:
expr .
呢?
有了优先级,bison就可以比较递进与规约的选择间涉及的优先级;看到*的优先级比+高,于是选择递进。
而在calc2.y中,加减乘除幂这几个带优先级的运算符堆在了binop规则中。匹配该规则其实不需要优先级,单靠lookahead就足够了;在遇到加减乘数幂这几个运算符时,bison肯定会选择规约为binop;规约后,binop本身就不带有任何优先级信息了。而在expr规则中,需要优先级去区分递进或规约的expr binop expr子规则却得不到任何优先级信息,于是递进/规约冲突又冒出来了。
phyeas的问题:
phyeas 写道
另外,想问下如果我在声明处定义如下:
%left PLUS
然后在规则处:
expression:
expression op expression
;
op:
PLUS
;
这样的华expression是否会应用上面定义的优先级?
%left PLUS
然后在规则处:
expression:
expression op expression
;
op:
PLUS
;
这样的华expression是否会应用上面定义的优先级?
答案是:不会。
进一步阅读:
首推自然是bison的手册。
这个帖子也可以读读,也是用表达式计算器为例子来讲解的。现在好困,不想码那么多字,既然有现成的解释我也就不用码了 =v=
- test_bison.zip (26.9 KB)
- 下载次数: 16
发表评论
-
Sun JDK1.4.2_28有TieredCompilation
2014-05-12 08:48 0原来以前Sun的JDK 1.4.2 update 28就已经有 ... -
IBM JVM notes (2014 ver)
2014-05-11 07:16 0Sovereign JIT http://publib.bou ... -
HotSpot Server Compiler与data-flow analysis
2014-01-07 17:41 0http://en.wikipedia.org/wiki/Da ... -
基于LLVM实现VM的JIT的一些痛点
2014-01-07 17:25 0同事Philip Reames Sanjoy Das http ... -
《自制编程语言》的一些笔记
2013-11-24 00:20 0http://kmaebashi.com/programmer ... -
对C语义的for循环的基本代码生成模式
2013-10-19 23:12 21729之前有同学在做龙书(第二版)题目,做到8.4的练习,跟我对答案 ... -
Nashorn各种笔记
2013-07-15 17:03 0http://bits.netbeans.org/netbea ... -
《深入理解Java虚拟机(第二版)》书评
2013-07-08 19:19 0值得推荐的中文Java虚拟机入门书 感谢作者赠与的样书,以下 ... -
豆列:从表到里学习JVM实现
2013-06-13 14:13 48100刚写了个学习JVM用的豆列跟大家分享。 豆列地址:http: ... -
Building Blocks of a JavaScript Engine
2013-05-23 00:49 0sketches of my new book "B ... -
读《JavaScript语言精髓与编程实践(第二版)》
2013-05-21 00:32 02008年逛书店的时候偶 ... -
添加一个bool C1LateInline参数?
2011-11-25 16:03 0之前我试过给Phi加exact_type不行,那如果像C2一样 ... -
别测空循环
2011-06-23 21:56 5155今天有朋友提到一个叫 ReflectASM的库,为Java环境 ... -
javac在编译创建内部类对象时生成的奇怪的getClass()调用是什么?
2011-06-14 22:17 4171有人问下面这段代码里,main()方法里的outer.new ... -
confluence property
2011-06-08 20:41 0http://en.wikipedia.org/wiki/Co ... -
JIT编译找不到类?
2011-05-09 22:28 5116今天开始Sun的老blog真的搬迁了,从blogs.sun.c ... -
几个简答题
2011-01-10 16:08 2410某题目 写道 龙书 写道In addition to a c ... -
循环中的字符串拼接的优化
2010-12-09 20:46 0public class StringConcatDemo { ... -
Velocity模板的编译
2010-11-15 14:49 0http://ecee.colorado.edu/ecen45 ... -
ANTLR里迭代子规则的一个注意点
2010-09-27 15:31 3554这几天在休假在家,有空的时候在用ANTLR 3.2来写D 2. ...
相关推荐
基于Floyd运算符优先级语法的PArallel PArser GENeratOr PAPAGENO是功能强大且高效的并行解析器生成器。 它从语法规范开始以与Bison相同的语法生成并行C解析器。 生成的解析器是独立的,可以与常见的GNU Flex生成...
centos7离线安装bison
GNU bison是一个自由软件,用于自动生成语法分析器程序,实际上可用于所有常见的操作系统。Bison把LALR形式的上下文无关文法描述转换为可做语法分析的C或C++程序。在新近版本中,Bison增加了对GLR语法分析算法的支持...
使用flex和bison开发了一个具有全部功能的桌面计算器,能够支持变量,过程,循环和条件表达式,使它成为一个虽然短小但是具有现实意义的编译器。重点学习抽象语法树的用法,它具有强大而简单的数据结构来表示分析...
bison
Visual Studio中创建Flex+Bison项目,源码中包含多个vs2010可编译通过的demo,用win_flex_bison-2.5.18 其中包含《Visual Studio中创建Flex+Bison项目.pdf》学习flex bison入门资料《flex与bison中文版.pdf》
中文版可以参考如下:http://www.kumouse.com/doc/bison/bison.html
bison-3.0.tar.gz 在安装wine过程中可能遇到bison版本不合,现给出目前最新版本bison。
binso2.4.1 for windows setup url:http://gnuwin32.sourceforge.net/packages/bison.htm
利用附录提供的 C 语言文法的相关参考资料,利用 Yacc/Bison 编写一个 C 语言分析器。利用附录提供的 C 语言文法的相关参考资料,利用 Yacc/Bison 编写一个 C 语言分析器。
此压缩包中包含flex和bison两个安装程序,是qgis编译所需的两个必备安装包。
bison官方手冊
Bison 官方参考手册英文版!
原版Flex and Bison,强大的语法分析工具,本书主要用于入门的。 想深入的话需要结合项目或分析一些开源软件的实际应用,flex和bison在开源软件中应用还是挺广的,像内核的dts描述文件,iptables的指令语法均是通过...
GNU Bison 中文手册。 中文翻译作者: Naga Bank。
GNU bison 是属于 GNU 项目的一个语法分析器生成器。Bison 把一个关于“向前查看 从左到右 最右”(LALR) 上下文无关文法的描述转化成可以分析该文法的 C 或 C++ 程序。它也可以为二义文法生成 “通用的 从左到右 最...
Linux下的flex+bison1
使用flex和bison开发了一个具有全部功能的桌面计算器,能够支持变量,过程,循环和条件表达式,使它成为一个虽然短小但是具有现实意义的编译器。重点学习抽象语法树的用法,它具有强大而简单的数据结构来表示分析...
bison.simple文件,自己用MinGW编译flex和bison又没那个能力,只好找一些第三方的port,好在终于让我找到了一个,虽然比较老,但是用于学习编译原理还是够了:)