解析中的優先級

我重新提出了一個我以前問過的問題。目的是瞭解優先級在解析中的工作原理。解析中的優先級

我想解析一條語句a(3).value = 100。 parser.mly在閱讀.後停止，並返回錯誤。

但是，如果我將竭誠爲argument_list部分（由begin和end EN-globed）在文件的結尾（因此是l_expression）之後，解析效果很好。

在語句被解析的情況下，它被簡化爲let_statement的data_manipulation_statement; a(3).value減至member_access_expression; a(3)減少到index_expression;和3減少到argument_list。

在無法解析語句的情況下，它似乎試圖將語句的開頭減少到control_statement的call_statement ......它以錯誤結束。

我一直認爲，無論優先級是什麼，解析總是會拒絕不能以成功結束的減少。但在那裏，似乎它嘗試和失敗，並拒絕嘗試其他可能性...

任何人都可以幫助澄清？

statement: 
| control_statement { $1 } 
| data_manipulation_statement { BS_DMS $1 } 

control_statement: | control_statement_except_multiline_if { BS_CSEMI $1 } 
control_statement_except_multiline_if: | call_statement { $1 } 
call_statement: | simple_name_expression argument_list { CSEMI_SNE_AL ($1, $2) } 
data_manipulation_statement: | let_statement { $1 } 
let_statement: | l_expression EQUAL expression { DMS_let (None, $1, $3) } 

simple_name_expression: | name { $1 } 
index_expression: | l_expression LPAREN argument_list RPAREN { IE_LE_AL ($1, $3) } 
member_access_expression: | l_expression DOT unrestricted_name { MAE_LE_UN ($1, $3) } 
literal_expression: | INTEGER { LIE_INT $1 } 

unrestricted_name: | name { UN_N $1 } 
name: | untyped_name { N_UN $1 } 
untyped_name: | IDENTIFIER { UN_I $1 } 

expression: 
| l_expression { E_LE $1 } 
| value_expression { E_VE $1 } 

value_expression: 
| literal_expression { VE_LIE $1 } 
| parenthesized_expression { VE_PE $1 } 

(***** begin argument_list *****) 
argument_list: | positional_or_named_argument_list { AL_PONAL $1 } 

positional_or_named_argument_list: 
| positional_argument_COMMAs required_positional_argument { PONAL_PAs_RPA (List.rev $1, $2) } 
positional_argument_COMMAs: 
    /* empty */ { [] } 
| positional_argument_COMMAs positional_argument COMMA { $2 :: $1 } 

positional_argument: | argument_expression { $1 } 
required_positional_argument: | argument_expression { $1 } 
argument_expression: | expression { AE_expression (None, $1) } 
(***** end argument_list *****) 

l_expression: 
| simple_name_expression { LE_SNE $1 } 
| index_expression { LE_IE $1 } 
| member_access_expression { LE_MAE $1 }

來源

2013-10-22 SoftTimur

關於解析過程如何進行並沒有絕對的規則。這取決於解析器。可以說，一個正確的解析器應該「總是拒絕不能以成功結束的縮小」，但通常不能用線性時間從左到右的解析器來完成。一個GLR解析器（野牛可以生成）可以做到這一點，可能達到立方時間，這取決於語法。回溯解析器 - 比如大多數解析組合庫 - 可以做到這一點，但要估計算法的複雜性並不容易。但是，根據您的標籤，我認爲您正在使用的* LR（1）解析器只能解析器* LR（1）語法，而您的語法不是其中之一。

LR（1）語法分析器一次從一個記號開始，從輸入的每個記號開始，從左到右（L）。在讀取每個令牌後，它會「減少」（即匹配產品）所有以輸入的最右側令牌（R）結束的產品。爲此，它使用盡可能多的信息，因爲它可以保留解析進程（「解析堆棧」）和下一個令牌（「超前」）。他們使用有限狀態下推自動機，並且有幾種構造這些自動機的方法，它們爲理想的PDA提供了不同的近似值，但是對於語法而言無關緊要。我相信ocamlyacc生成LALR（1）解析器，就像原始的yacc一樣，但是你的語法甚至不是LR（1），所以它肯定不能被簡化的LR（1）解析器解析。

在上面的描述中，我沒有使用「優先」這個詞，因爲它不適用於LR解析。有些優先級解析器 - 通常不如LR解析器強大，但也更容易構建 - 但除了手寫解析器外，它們不再那麼常見。（我不確定是否有優先級 - 語法分析器生成器;一旦發現LALR（1）分析，它就迅速接管了分析器生成器市場，因爲它比優先級或LL（1）分析更強大。）然而，爲了應對模糊的語法，在其發展的一些早期階段，「優先級」被添加到yacc;或者通常是可能已經明確寫入但是其模糊形式更緊湊的語法。

當LR解析器決定要做什麼時，可能有多個備選項。這可能是因爲不止一種可能的減少（「減少 - 減少」衝突），或者不清楚可用減少是否正確（「減少 - 減少」衝突）。衝突產生是因爲語法不明確，或者因爲它不能用僅僅指定的預覽進行LR分析。

無論是哪一種情況，迂腐的LR解析器生成器都會報告失敗。但是一個實用的解析器生成器可能試圖找出哪個替代方案是所需的解決方案，並據此進行。這樣做的一個簡單方法是根據程序員提供的一些聲明（「優先聲明」）或者基於某種啓發式（「首選語法文件中首先出現的內容」），給予另一種優先權，）。這樣的啓發式方法是危險的，因爲它們可能導致解析器無法真正解析您希望解析的語言;恕我直言，沒有解析器生成器應該應用啓發式，至少警告你它已經這樣做了。

現在，實際問題：爲什麼你的語法不是LR（1）。

讓我們從下面的摘錄開始。

call_statement: simple_name_expression argument_list 
let_statement: l_expression EQUAL expression 
l_expression: index_expression 
l_expression: simple_name_expression 
index_expression: l_expression LPAREN argument_list RPAREN

現在考慮輸入：a (。也就是說，我們剛剛讀取了令牌a，並且前瞻令牌爲(。 a必須減少到simple_name_expression（通過幾個單位的製作，但細節無關緊要）。現在，在這一點上，解析器的狀態將包括：（·表示在生產中目前的「點」）：

call_statement: simple_name_expression · argument_list 
index_expression: l_expression · LPAREN argument_list RPAREN 
l_expression:  simple_name_expression ·

也就是說，我們可以離開simple_name_expression，因爲它是和繼續收集argument_list，或我們可以將simple_name_expression減少到l_expression，以便繼續收集index_expression的其餘部分。哪一個？

不幸的是，我們無法知道答案，直到至少達到匹配RPAREN時。即使這樣，我們可能也不知道答案，因爲下一個令牌可能會擴展l_expression（例如.或另一個LPAREN），在這種情況下，我們需要繼續掃描。沒有什麼時候我們會找到答案，所以沒有有限的前瞻就足夠了，這個語法 - 儘管可能是明確的 - 對任何k都不是LR（k）。（並且優先啓發法也行不通。）

順便說一下，我不清楚你的語法是否是你想要的call_statement。一個argument_list可以用（開始，因爲它必須以expression開始和expression可以括號，但它並沒有開始一個括號所以下面將是一個合法的call_statement：

print a(3), value

如果這就是你想要的，很好。

來源

2013-10-22 21:20:53 rici

解析中的優先級

回答

相關問題