假設文法 G 有以下產生式……
- S → aSb | 一個 | 乙
- A → λ | 一個 | 啊 | 啊啊啊
- B → bB | b
使用語法 G，字串aaaaabb的派生是……
S ? aSb ? aaSbb ? aaAbb ? aaaaabb
在下圖的 Raku 語法中，為什么字串aaaaabb決議不成功？上面顯示的推導不適用嗎？
# Goal: language generated by grammar = { a^n b^m : n <= m 3 }
# Example string is:
# aaaaabb = a^5 b^2, where 5 <= 2 3
# Derivation of string aaaaabb is:
# S => aSb => aaSbb => aaAbb => aaaaabb
grammar MyContextFreeGrammar
{
token TOP { <S> }
token S { 'a' <S> 'b' | <A> | <B> }
token A { '' | 'a' | 'a' 'a' | 'a' 'a' 'a' }
token B { 'b' <B> | 'b' }
} # end grammar
my $abString = 'aaaaabb';
my $myParseResult = MyContextFreeGrammar.parse( $abString ) ;
if $myParseResult.Bool
{
printf( "\nParsing of \'%s\' was *SUCCESSFUL*.\n", $abString ) ;
}
else
{
printf( "\nParsing of \'%s\' was *NOT* successful.\n", $abString ) ;
}
程式輸出是……
Parsing of 'aaaaabb' was *NOT* successful.
更新
Raku 檔案 ( https://docs.raku.org/language/grammars) 表明……
（宣告符token和rule）都是棘輪的，這意味著匹配引擎不會備份并在匹配失敗時重試。
下面顯示的修改后的語法 - 它利用regex而不是token- 允許回溯并按照兩個測驗字串aaaaabb （它是由語法 G 生成的語言）和aaaaaabb （它不是由語法 G 生成的語言） ......
grammar MyContextFreeGrammar
{
regex TOP { <S> }
regex S { 'a' <S> 'b' | <A> | <B> }
regex A { '' | 'a' | 'a' 'a' | 'a' 'a' 'a' }
regex B { 'b' <B> | 'b' }
} # end grammar
my $abString = 'aaaaabb';
my $myParseResult = MyContextFreeGrammar.parse( $abString ) ;
printf( "\nParsing of \'%s\' was "
~ ($myParseResult ?? "*SUCCESSFUL*.\n" !! "*NOT* successful.\n" ),
$abString ) ;
$abString = 'aaaaaabb';
$myParseResult = MyContextFreeGrammar.parse( $abString ) ;
printf( "\nParsing of \'%s\' was "
~ ($myParseResult ?? "*SUCCESSFUL*.\n" !! "*NOT* successful.\n" ),
$abString ) ;
程式輸出是……
Parsing of 'aaaaabb' was *SUCCESSFUL*.
Parsing of 'aaaaaabb' was *NOT* successful.
uj5u.com熱心網友回復：
Raku 語法是決議器，而不是生成語法
問題示例的自然慣用解決方案：
grammar S { token TOP { (a*) (b*) <?{ $0.chars <= $1.chars 3 }> } }
這直接在決議器中對示例的描述進行編碼—— token1 進行零個或多個as 的匹配/捕獲，然后是零個或多個 s 的匹配/捕獲b，最后是與示例公式相對應的謂詞檢查。
測驗代碼和結果：
say "$_: {so S.parse: $_}" for ^9 .map: { 'a' x $_ ~ 'bb' }
bb: False
abb: True
aabb: True
aaabb: True
aaaabb: True
aaaaabb: True
aaaaaabb: False
aaaaaaabb: False
aaaaaaaabb: False
可以將生成語法與 Raku 一起使用，就像將它們與任何其他 PL 一起使用一樣。
但是 Raku 的愿景和使命包括可以組合的一流語法（和語法片段）。
如果組合兩個或多個生成 CFG，即使組成語法明確，結果也可能不明確。沒有演算法可以檢測結果是否不明確，因此如果合成產生此結果，甚至不會出現警告或錯誤。
因此生成語法不能用于其內置 grammar構造。
需要明確的是，語法作文不僅是一種非常好的東西，而且在日益多語言的世界中變得越來越重要。人們希望能夠做一些事情，比如在 GPL 代碼中嵌入 SQL。怎么辦？如果 SQL 在字串中，您將受到注入攻擊。Larry Wall 決定必須有一種更好的方法，一種有原則的方法：可組合語法。
參考我在 reddit 執行緒Ergonomic inline SQL as a Python library中的評論。兩個關鍵摘錄：
（我忘了提到的一個關鍵點，這可能不是很明顯，Raku 俚語在編譯時是完全集成的。因此可能存在編譯時語法、型別等錯誤，并且完全防御注入攻擊，這是一個如果 DSL（例如 SQL）在字串中，則要困難得多。）
哇，我不知道存在這種語言“編織”的想法。感謝分享一點點樂。“sql insert into ...; with”這一行特別酷，因為您實際上是在用非常少的語法噪音撰寫多種語言。
腳注
1token宣告者意味著棘輪：
棘輪可以是一種優化，因為回溯成本很高。但更重要的是，它與人類決議文本的方式密切相關。
該檔案沒有提到另一個重要方面：消除（風險）災難性回溯。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/518409.html
標籤：解析语法乐