高科技啊。。 樓主牛13  回復  更多評論
  

牛人！  回復  更多評論
  

好東西.  回復  更多評論
  

請教樓主一個問題。既然語法分析里的lr1算法那么好用，為什么編譯原理每一本教科書里都還保留著ll(1)的內容。是不是ll(1)在實際應用中有比lr(1)優勢的地方。還是僅僅是它比較適合初學者學習，而在實際應用中與lr比較一無是處？到底有沒有從ll(1)開始學習的必要？  回復  更多評論
  

@ooseven
你不認為這樣做理解會深刻一點么  回復  更多評論
  

請問博主，這個自動機是lair(1)? , 它是在編譯期生成還是在執行期呢？
boost::spirit是在編譯期生成還是在執行器呢？先謝謝了。  回復  更多評論
  

呵呵，我把博主當成老師了，沒辦法水平比較差，請老師多多包涵。我還有一個問題。正則語法中大部分操作的意思與ebnf或abnf的意思是一樣的，不知道為什么ebnf或abnf要標新立異？
比如正則文法中的 *, + ,{ 、}, ?
分別可對應于上下文無關文法中的:
元素* = {元素}
元素+ = 元素,{元素}
元素{1,2} = ebnf沒有相對應，abnf中有 1*2元素
元素? = [元素]

二者的文法所表達的意思完全一樣，但是形式不統一，給開發分析器的同學增加了工作量。我想問的是這么做有什么原因嗎？  回復  更多評論
  

歷史原因  回復  更多評論
  

你很強我佩服你，但是你能不能不用unicode編碼。vc6完全打不開。  回復  更多評論
  

@dingding
不能  回復  更多評論
  

陳梓瀚兄還沒解答我的問題呢，你這個分析器的自動機是用元編程于編譯期生成的還是在執行期才生成呢？  回復  更多評論
  

@林林
大部分編譯期生成，循環嵌套的由執行期生成并做垃圾收集。  回復  更多評論
  

陳大俠好：
請教大俠一個問題，我已經完成了一個初級可用的LALR(1)語法分析引擎，里面包含了詞法分析，并且設計了ide界面。正在爽的時候，卻被一個不起眼的小問題給難到了。就是當發現錯誤的時候，如何實時的與窗口界面交互？一般來說編譯器都允許出現錯誤的情況下繼續編譯，如果在dos的界面下就簡單了，一個printf語句就解決問題，但在窗口下就麻煩了。如果直接向窗口發送消息，就會引起引擎與界面代碼混在一起的引起人們詬病的設計，如果用throw那么就只允許發生一次錯誤。如果這樣的話，那錯誤恢復策略就白做了！，不知道有沒有什么好的解決方案啊！
感謝您白忙之中的恢復
敬禮！
2009/08/01
來自廈門。  回復  更多評論
  

@ooseven
用Observer模式  回復  更多評論
  

Observer模式！馬上去學習，謝謝大俠！  回復  更多評論
  

看了一下observer模式，其實沒什么稀奇，我以前做的工程中就實現了這種思路，只不過不知道這就是observer模式。但是，這種模式不適合作為語法分析引擎與ide的交互吧？
三個理由：
1、還是要包含窗口句柄，只不過改到一個單獨的類里的觀測者鏈表中。
2、語法分析引擎不需要同時與多個窗口交互，只需要與一個窗口交互就
夠了。
3、還是免不了sendmessge，而ide要注冊這個自定義的message,然后在
這個消息里接收。
耦合得太厲害了，用了observer后簡直就是變本加厲！
不過我倒是在網上看到了一種方案，就是ide端通過創建一線程，在線程里創建命名管道監聽stderr，從而達到實時接收引擎消息的目的。這種方式雖然在ide端工作量不小，但由于其通用性強，可以封裝成一個類。更主要的是引擎端根本就直接printf 到stderr就行了。
到目前為止，這是我覺得的最好的方案了，不知道還有沒有更好的方案！  回復  更多評論
  

@ooseven
難道監聽stderr就不是observer？  回復  更多評論
  

@陳梓瀚(vczh)
observer不是處理一個消息源對多個訂閱者發行的關系模型嗎?,多個訂閱者一起預約，一旦有消息發生，就通知全部的訂閱者。可是，我這里只有一個窗口需要得到引擎的stderr消息啊?  回復  更多評論
  

@林林
不要搞教條主義和本本主義。  回復  更多評論
  

請教陳兄一個問題：
邏輯表達式結合算術表達式的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 ;
}  回復  更多評論
  

改成下面這樣子之后，就只剩下上面那個移進與歸約沖突了

%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 ;
}  回復  更多評論
  

發現問題在于 當邏輯表達式也要支持(logic_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;

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 ;
}  回復  更多評論
  

最新問題！
問題在于這條產生式：
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 ;
}



  回復  更多評論
  

@林林
別刷屏，你應該這么寫：
(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)* [;]  回復  更多評論
  

@陳梓瀚(vczh)
問題解決了，謝謝陳兄的指導！
最終是通過%right,與優先級來解決的  回復  更多評論
  

通過%right 解決了else的移進與歸約沖突
通過符號的優先級，解決了ifstmt else 與statement : ifstmt的歸約與歸約沖突  回復  更多評論
  

請教陳兄：
一般的腳本引擎有沒有必要編譯成字節碼在虛擬機或簡單的堆棧機里運行？還是直接在語法樹里純解析運行就可以了，速度差很多嗎？
如果有一個腳本引擎，沒有源代碼，有沒有什么辦法得知它是純解析運行還是在編譯成字節碼然后才運行？  回復  更多評論
  

@林林
1：一般生成指令就足夠了，至于指令是struct的數組還是vector還是字節碼那其實沒有多大區別。
2：沒有辦法。
3：速度的瓶頸一般在腳本的對象的內存分配以及調用一個名字的時候查找的過程。  回復  更多評論
  

@陳梓瀚(vczh)
經過了一個早上的優化后，現在的結果是329.032秒，雖然還是很慢，但是已經很開心了！
cpu e6600
內存 2g

經過測試，vc2008 debug下的運行時間是2秒
vc2008 release下的運行時間是0秒
天啊，太塊了！
陳兄不削拿您的虛擬機跟我比，可以理解。但拿出來跟vc比比總不會辱沒了您的身份吧:)
我說的是虛擬機，而不實您翻譯成機器碼后拿來比較哦  回復  更多評論
  

@ooseven
我那個生成的代碼比較垃圾，肯定比debug慢。  回復  更多評論
  

@ooseven
用Reactive Style來做，類似Rx那樣  回復  更多評論
  

@U2U
combinator比rx更合適……  回復  更多評論
  

Reactive Style應該是可以的  回復  更多評論