随笔-341  评论-2670  文章-0  trackbacks-0
    对上一次的分析器进行重构之后,Combinator Parser加入了对字符串、词法分析器以及正则表达式的新支持。功能上则添加了对于歧义和非歧义的控制。Demo代码结构如下:

    <Library>
        <Data>
            <Data>数据结构
            <Grammar2>正则表达式源代码
                <Combinator>文法分析器
    <Demo>例子以及可以在Visual Studio 2008下编译的工程

    下面是执行的截图:


    点击这里下载。
posted on 2009-04-06 22:18 陈梓瀚(vczh) 阅读(8928) 评论(34)  编辑 收藏 引用 所属分类: 作品

评论:
# re: C++轻量级文法分析器更新,代码+DEMO×3(下载) 2009-04-07 09:04 | 1shou
高科技啊。。 楼主牛13  回复  更多评论
  
# re: C++轻量级文法分析器更新,代码+DEMO×3(下载) 2009-04-08 00:28 | shiweifu
牛人!  回复  更多评论
  
# re: C++轻量级文法分析器更新,代码+DEMO×3(下载)[未登录] 2009-04-11 16:42 | jans2002
好东西.  回复  更多评论
  
# re: C++轻量级文法分析器更新,代码+DEMO×3(下载) 2009-04-21 22:00 | ooseven
请教楼主一个问题。既然语法分析里的lr1算法那么好用,为什么编译原理每一本教科书里都还保留着ll(1)的内容。是不是ll(1)在实际应用中有比lr(1)优势的地方。还是仅仅是它比较适合初学者学习,而在实际应用中与lr比较一无是处?到底有没有从ll(1)开始学习的必要?  回复  更多评论
  
# re: C++轻量级文法分析器更新,代码+DEMO×3(下载) 2009-04-21 23:47 | 陈梓瀚(vczh)
@ooseven
你不认为这样做理解会深刻一点么  回复  更多评论
  
# re: C++轻量级文法分析器更新,代码+DEMO×3(下载) 2009-04-29 08:33 | 林林
请问博主,这个自动机是lair(1)? , 它是在编译期生成还是在执行期呢?
boost::spirit是在编译期生成还是在执行器呢?先谢谢了。  回复  更多评论
  
# re: C++轻量级文法分析器更新,代码+DEMO×3(下载) 2009-04-29 15:41 | 林林
呵呵,我把博主当成老师了,没办法水平比较差,请老师多多包涵。我还有一个问题。正则语法中大部分操作的意思与ebnf或abnf的意思是一样的,不知道为什么ebnf或abnf要标新立异?
比如正则文法中的 *, + ,{ 、}, ?
分别可对应于上下文无关文法中的:
元素* = {元素}
元素+ = 元素,{元素}
元素{1,2} = ebnf没有相对应,abnf中有 1*2元素
元素? = [元素]

二者的文法所表达的意思完全一样,但是形式不统一,给开发分析器的同学增加了工作量。我想问的是这么做有什么原因吗?  回复  更多评论
  
# re: C++轻量级文法分析器更新,代码+DEMO×3(下载) 2009-04-30 11:04 | 陈梓瀚(vczh)
历史原因  回复  更多评论
  
# re: C++轻量级文法分析器更新,代码+DEMO×3(下载) 2009-05-14 15:47 | dingding
你很强我佩服你,但是你能不能不用unicode编码。vc6完全打不开。  回复  更多评论
  
# re: C++轻量级文法分析器更新,代码+DEMO×3(下载) 2009-05-14 18:01 | 陈梓瀚(vczh)
@dingding
不能  回复  更多评论
  
# re: C++轻量级文法分析器更新,代码+DEMO×3(下载) 2009-05-15 16:43 | 林林
陈梓瀚兄还没解答我的问题呢,你这个分析器的自动机是用元编程于编译期生成的还是在执行期才生成呢?  回复  更多评论
  
# re: C++轻量级文法分析器更新,代码+DEMO×3(下载) 2009-05-15 20:33 | 陈梓瀚(vczh)
@林林
大部分编译期生成,循环嵌套的由执行期生成并做垃圾收集。  回复  更多评论
  
# re: C++轻量级文法分析器更新,代码+DEMO×3(下载) 2009-08-01 20:08 | ooseven
陈大侠好:
请教大侠一个问题,我已经完成了一个初级可用的LALR(1)语法分析引擎,里面包含了词法分析,并且设计了ide界面。正在爽的时候,却被一个不起眼的小问题给难到了。就是当发现错误的时候,如何实时的与窗口界面交互?一般来说编译器都允许出现错误的情况下继续编译,如果在dos的界面下就简单了,一个printf语句就解决问题,但在窗口下就麻烦了。如果直接向窗口发送消息,就会引起引擎与界面代码混在一起的引起人们诟病的设计,如果用throw那么就只允许发生一次错误。如果这样的话,那错误恢复策略就白做了!,不知道有没有什么好的解决方案啊!
感谢您白忙之中的恢复
敬礼!
2009/08/01
来自厦门。  回复  更多评论
  
# re: C++轻量级文法分析器更新,代码+DEMO×3(下载) 2009-08-02 18:30 | 陈梓瀚(vczh)
@ooseven
用Observer模式  回复  更多评论
  
# re: C++轻量级文法分析器更新,代码+DEMO×3(下载) 2009-08-02 20:58 | ooseven
Observer模式!马上去学习,谢谢大侠!  回复  更多评论
  
# re: C++轻量级文法分析器更新,代码+DEMO×3(下载) 2009-08-02 21:47 | ooseven
看了一下observer模式,其实没什么稀奇,我以前做的工程中就实现了这种思路,只不过不知道这就是observer模式。但是,这种模式不适合作为语法分析引擎与ide的交互吧?
三个理由:
1、还是要包含窗口句柄,只不过改到一个单独的类里的观测者链表中。
2、语法分析引擎不需要同时与多个窗口交互,只需要与一个窗口交互就
够了。
3、还是免不了sendmessge,而ide要注册这个自定义的message,然后在
这个消息里接收。
耦合得太厉害了,用了observer后简直就是变本加厉!
不过我倒是在网上看到了一种方案,就是ide端通过创建一线程,在线程里创建命名管道监听stderr,从而达到实时接收引擎消息的目的。这种方式虽然在ide端工作量不小,但由于其通用性强,可以封装成一个类。更主要的是引擎端根本就直接printf 到stderr就行了。
到目前为止,这是我觉得的最好的方案了,不知道还有没有更好的方案!  回复  更多评论
  
# re: C++轻量级文法分析器更新,代码+DEMO×3(下载) 2009-08-03 00:15 | 陈梓瀚(vczh)
@ooseven
难道监听stderr就不是observer?  回复  更多评论
  
# re: C++轻量级文法分析器更新,代码+DEMO×3(下载) 2009-08-03 09:16 | 林林
@陈梓瀚(vczh)
observer不是处理一个消息源对多个订阅者发行的关系模型吗?,多个订阅者一起预约,一旦有消息发生,就通知全部的订阅者。可是,我这里只有一个窗口需要得到引擎的stderr消息啊?  回复  更多评论
  
# re: C++轻量级文法分析器更新,代码+DEMO×3(下载) 2009-08-05 15:13 | 陈梓瀚(vczh)
@林林
不要搞教条主义和本本主义。  回复  更多评论
  
# re: C++轻量级文法分析器更新,代码+DEMO×3(下载) 2009-08-17 08:54 | 林林
请教陈兄一个问题:
逻辑表达式结合算术表达式的bnf怎么写啊,我写的怎么都有冲突!
要实现的功能很简单:
实现:
1、 a+1>0 Or b*10
2、 a*9>0 Or b
第一条语句的bnf没问题,问题在于当第二条语句的bnf加进去的时候出现两个冲突。
第一个移进与归约冲突在于,当出现')'的时候有一个移进,移进到一个新的状态,该状态有一个归约arithmetic_factor : '(' arithmetic_exp ')'。或者直接归约compare_exp : arithmetic_exp

第二个归约与归约冲突在于,当遇到'$'的时候,是以program : arithmetic_exp归约,还是以compare_exp : arithmetic_exp归约。
我搞不定!请陈兄百忙之中,抽空看看啊!

%lextest
{
%skip : <\s| |//[^\r\n]+>
IF : <if>
ELSE : <else>
WHILE : <while>
BREAK : <break>
CONTINUE : <continue>
RETURN : <return>
'(' : <\(>
')' : <\)>
'*' : <\*>
'/' : <\/>
'+' : <\+>
'-' : <\->
ISEQUAL : <==>
ISNOTEQUAL : <!=>
GREATER : <\>>
GREATEROREQUAL : <>=>
LESSER : <<>
LESSEROREQUAL : <<=>
NOT : <Not>
AND : <And>
OR : <Or>
NUMBER : <[0-9]+(\.[0-9])*>
VARIABLENAME : <[a-zA-Z][a-zA-Z0-9]*>
STRING : <"[^\r\n]+">
}
%syntax
{
%terminator_type {int}
program : logic_exp
| arithmetic_exp ;


logic_exp : logic_exp OR logic_and_term
| logic_and_term;
logic_and_term : logic_and_term AND logic_not_term
| logic_not_term;
logic_not_term : NOT logic_factor
| logic_factor;
logic_factor : '(' logic_exp ')'
| compare_exp;

compare_exp : compare_exp ISEQUAL arithmetic_exp
| compare_exp ISNOTEQUAL arithmetic_exp
| compare_exp GREATER arithmetic_exp
| compare_exp GREATEROREQUAL arithmetic_exp
| compare_exp LESSER arithmetic_exp
| compare_exp LESSEROREQUAL arithmetic_exp
| arithmetic_exp;

arithmetic_exp : arithmetic_exp '+' arithmetic_term
| arithmetic_exp '-' arithmetic_term
| arithmetic_term;

arithmetic_term : arithmetic_term '*' arithmetic_factor
| arithmetic_term '/' arithmetic_factor
| arithmetic_factor;

arithmetic_factor : '(' arithmetic_exp ')'
| NUMBER
| VARIABLENAME ;
}  回复  更多评论
  
# re: C++轻量级文法分析器更新,代码+DEMO×3(下载) 2009-08-17 09:01 | 林林
改成下面这样子之后,就只剩下上面那个移进与归约冲突了

%lextest
{
%skip : <\s| |//[^\r\n]+>
IF : <if>
ELSE : <else>
WHILE : <while>
BREAK : <break>
CONTINUE : <continue>
RETURN : <return>
'(' : <\(>
')' : <\)>
'*' : <\*>
'/' : <\/>
'+' : <\+>
'-' : <\->
ISEQUAL : <==>
ISNOTEQUAL : <!=>
GREATER : <\>>
GREATEROREQUAL : <>=>
LESSER : <<>
LESSEROREQUAL : <<=>
NOT : <Not>
AND : <And>
OR : <Or>
NUMBER : <[0-9]+(\.[0-9])*>
VARIABLENAME : <[a-zA-Z][a-zA-Z0-9]*>
STRING : <"[^\r\n]+">
}
%syntax
{
%terminator_type {int}

program : ifstmt ;

ifstmt : IF '(' logic_exp ')' arithmetic_exp
| IF '(' logic_exp ')' arithmetic_exp ELSE arithmetic_exp
| IF '(' logic_exp ')' arithmetic_exp ELSE ifstmt ;

logic_exp : logic_exp OR logic_and_term
| logic_and_term;
logic_and_term : logic_and_term AND logic_not_term
| logic_not_term;
logic_not_term : NOT logic_factor
| logic_factor;
logic_factor : '(' logic_exp ')'
| compare_exp;

compare_exp : compare_exp ISEQUAL arithmetic_exp
| compare_exp ISNOTEQUAL arithmetic_exp
| compare_exp GREATER arithmetic_exp
| compare_exp GREATEROREQUAL arithmetic_exp
| compare_exp LESSER arithmetic_exp
| compare_exp LESSEROREQUAL arithmetic_exp
| arithmetic_exp;

arithmetic_exp : arithmetic_exp '+' arithmetic_term
| arithmetic_exp '-' arithmetic_term
| arithmetic_term;

arithmetic_term : arithmetic_term '*' arithmetic_factor
| arithmetic_term '/' arithmetic_factor
| arithmetic_factor;

arithmetic_factor : '(' arithmetic_exp ')'
| NUMBER
| VARIABLENAME ;
}  回复  更多评论
  
# re: C++轻量级文法分析器更新,代码+DEMO×3(下载) 2009-08-17 09:18 | 林林
发现问题在于 当逻辑表达式也要支持(logic_exp )优先级的时候,就会有冲突!  回复  更多评论
  
# re: C++轻量级文法分析器更新,代码+DEMO×3(下载) 2009-08-17 09:58 | 林林
经过了下面的修改,已经通过!!!,哈,高兴
%lextest
{
%skip : <\s| |//[^\r\n]+>
IF : <if>
ELSE : <else>
WHILE : <while>
BREAK : <break>
CONTINUE : <continue>
RETURN : <return>
'(' : <\(>
')' : <\)>
'*' : <\*>
'/' : <\/>
'+' : <\+>
'-' : <\->
ISEQUAL : <==>
ISNOTEQUAL : <!=>
GREATER : <\>>
GREATEROREQUAL : <>=>
LESSER : <<>
LESSEROREQUAL : <<=>
NOT : <Not>
AND : <And>
OR : <Or>
NUMBER : <[0-9]+(\.[0-9])*>
VARIABLENAME : <[a-zA-Z][a-zA-Z0-9]*>
STRING : <"[^\r\n]+">
}
%syntax
{
%terminator_type {int}

program : logic_exp;

logic_exp : logic_exp OR logic_and_term
| logic_and_term;
logic_and_term : logic_and_term AND logic_not_term
| logic_not_term;
logic_not_term : NOT compare_exp
| compare_exp;

compare_exp : compare_exp ISEQUAL arithmetic_exp
| compare_exp ISNOTEQUAL arithmetic_exp
| compare_exp GREATER arithmetic_exp
| compare_exp GREATEROREQUAL arithmetic_exp
| compare_exp LESSER arithmetic_exp
| compare_exp LESSEROREQUAL arithmetic_exp
| arithmetic_exp;

arithmetic_exp : arithmetic_exp '+' arithmetic_term
| arithmetic_exp '-' arithmetic_term
| arithmetic_term;

arithmetic_term : arithmetic_term '*' arithmetic_factor
| arithmetic_term '/' arithmetic_factor
| arithmetic_factor;

arithmetic_factor : '(' logic_exp ')'
| NUMBER
| VARIABLENAME ;
}  回复  更多评论
  
# re: C++轻量级文法分析器更新,代码+DEMO×3(下载) 2009-08-17 11:25 | 林林
最新问题!
问题在于这条产生式:
statement : block
| sentence
| ifstmt
| whilestmt
| forstmt;
当加入了ifstmt,whilestmt,forstmt后出现了冲突!
可是,如果不加的话就不支持如下的语法:
if(a>0)
for(a=1 to 10) do
b = 10;
而一定要象这样
if(a>0)
begin
for(a=1 to 10) do
b=10;
end

很不爽啊! 怎么办!

以下是bnf文法:

%lextest
{
%skip : <\s| |//[^\r\n]+>
IF : <if>
ELSE : <else>
THEN : <then>
FOR : <for>
TO : <to>
DO : <do>
DOWNTO : <downto>
WHILE : <while>
BREAK : <break>
LOOP : <loop>
BEGIN : <begin>
END : <end>
';' : <;>
'(' : <\(>
')' : <\)>
'*' : <\*>
'/' : <\/>
'+' : <\+>
'-' : <\->
'=' : <=>
ISEQUAL : <==>
ISNOTEQUAL : <!=>
GREATER : <\>>
GREATEROREQUAL : <>=>
LESSER : <<>
LESSEROREQUAL : <<=>
NOT : <Not>
AND : <And>
OR : <Or>
NUMBER : <[0-9]+(\.[0-9])*>
VARIABLENAME : <[a-zA-Z][a-zA-Z0-9]*>
STRING : <"[^\r\n]+">
}
%syntax
{
%terminator_type {int}

program : ifstmt
|forstmt
|sentences
|whilestmt;

whilestmt : WHILE logic_exp DO circlestatement ;
forstmt : FOR assignment_exp TO logic_exp DO circlestatement
| FOR assignment_exp DOWNTO logic_exp DO circlestatement ;

circlestatement : circleblock
| circlesentence;
circleblock : BEGIN circlesentences END;
circlesentences : circlesentences circlesentence
| circlesentence ;
circlesentence : logic_exp ';'
| LOOP ';'
| BREAK ';';


ifstmt : IF '(' logic_exp ')' THEN statement
| IF '(' logic_exp ')' THEN statement ELSE statement
| IF '(' logic_exp ')' THEN statement ELSE ifstmt ;

statement : block
| sentence
| ifstmt
| whilestmt
| forstmt;
block : BEGIN sentences END;

sentences : sentences sentence
| sentence;
sentence : logic_exp ';'
| assignment_exp ';';

assignment_exp : VARIABLENAME '=' logic_exp;

logic_exp : logic_exp OR logic_and_term
| logic_and_term;
logic_and_term : logic_and_term AND logic_not_term
| logic_not_term;
logic_not_term : NOT compare_exp
| compare_exp;

compare_exp : compare_exp ISEQUAL arithmetic_exp
| compare_exp ISNOTEQUAL arithmetic_exp
| compare_exp GREATER arithmetic_exp
| compare_exp GREATEROREQUAL arithmetic_exp
| compare_exp LESSER arithmetic_exp
| compare_exp LESSEROREQUAL arithmetic_exp
| arithmetic_exp;

arithmetic_exp : arithmetic_exp '+' arithmetic_term
| arithmetic_exp '-' arithmetic_term
| arithmetic_term;

arithmetic_term : arithmetic_term '*' arithmetic_factor
| arithmetic_term '/' arithmetic_factor
| arithmetic_factor;

arithmetic_factor : '(' logic_exp ')'
| NUMBER
| STRING
| VARIABLENAME ;
}



  回复  更多评论
  
# re: C++轻量级文法分析器更新,代码+DEMO×3(下载) 2009-08-17 11:56 | 陈梓瀚(vczh)
@林林
别刷屏,你应该这么写:
(C++)
ifstmt = if (exp) stmt else stmt //我没有考虑那个经典问题
whilestmt = while (exp) stmt
...

stmt = (ifstmt | whilestmt) ;
stmt = { 很多stmt }
(PASCAL)
ifstmt = if exp then stmt else stmt;
whilestmt = while exp do stmt;
...
stmt = ifstmt | whilestmt
stmt = begin 很多stmt end
(PASCAL之可以省略最后一个分号)
ifstmt = if exp then stmt else stmt
whilestmt = while exp do stmt
...
stmt = ifstmt | whilestmt
stmt = begin stmt-list end
stmt-list = stmt (; stmt)* [;]  回复  更多评论
  
# re: C++轻量级文法分析器更新,代码+DEMO×3(下载) 2009-08-17 16:55 | 林林
@陈梓瀚(vczh)
问题解决了,谢谢陈兄的指导!
最终是通过%right,与优先级来解决的  回复  更多评论
  
# re: C++轻量级文法分析器更新,代码+DEMO×3(下载) 2009-08-17 16:56 | 林林
通过%right 解决了else的移进与归约冲突
通过符号的优先级,解决了ifstmt else 与statement : ifstmt的归约与归约冲突  回复  更多评论
  
# re: C++轻量级文法分析器更新,代码+DEMO×3(下载) 2009-08-18 10:05 | 林林
请教陈兄:
一般的脚本引擎有没有必要编译成字节码在虚拟机或简单的堆栈机里运行?还是直接在语法树里纯解析运行就可以了,速度差很多吗?
如果有一个脚本引擎,没有源代码,有没有什么办法得知它是纯解析运行还是在编译成字节码然后才运行?  回复  更多评论
  
# re: C++轻量级文法分析器更新,代码+DEMO×3(下载) 2009-08-18 12:31 | 陈梓瀚(vczh)
@林林
1:一般生成指令就足够了,至于指令是struct的数组还是vector还是字节码那其实没有多大区别。
2:没有办法。
3:速度的瓶颈一般在脚本的对象的内存分配以及调用一个名字的时候查找的过程。  回复  更多评论
  
# re: C++轻量级文法分析器更新,代码+DEMO×3(下载) 2009-08-25 19:33 | ooseven
@陈梓瀚(vczh)
经过了一个早上的优化后,现在的结果是329.032秒,虽然还是很慢,但是已经很开心了!
cpu e6600
内存 2g

经过测试,vc2008 debug下的运行时间是2秒
vc2008 release下的运行时间是0秒
天啊,太块了!
陈兄不削拿您的虚拟机跟我比,可以理解。但拿出来跟vc比比总不会辱没了您的身份吧:)
我说的是虚拟机,而不实您翻译成机器码后拿来比较哦  回复  更多评论
  
# re: C++轻量级文法分析器更新,代码+DEMO×3(下载) 2009-08-25 21:10 | 陈梓瀚(vczh)
@ooseven
我那个生成的代码比较垃圾,肯定比debug慢。  回复  更多评论
  
# re: C++轻量级文法分析器更新,代码+DEMO×3(下载) 2011-01-10 13:52 | U2U
@ooseven
用Reactive Style来做,类似Rx那样  回复  更多评论
  
# re: C++轻量级文法分析器更新,代码+DEMO×3(下载) 2011-01-10 18:57 | 陈梓瀚(vczh)
@U2U
combinator比rx更合适……  回复  更多评论
  
# re: C++轻量级文法分析器更新,代码+DEMO×3(下载) 2015-10-12 19:18 | chanel replica handbags
Reactive Style应该是可以的  回复  更多评论
  

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理