上下文無關語法與上下文敏感語法？

Question

有人可以向我解釋爲什麼這種類型的語法[context-free grammar和context-sensitive grammar]接受一個String？

我知道什麼是

上下文無關文法是一個正式的語法在每一個生產（重寫）規則爲V→W^ 的形式，其中V是一個非終結符和w是一個字符串終端和/或非終端。 W可以是空

上下文敏感的語法是正規的語法，其中左手側和任何生產（重寫）規則可以由終端和終結符的背景下所包圍的右手側。

但我怎麼能解釋爲什麼這些語法接受一個字符串？

Answer 1

顯示語法接受字符串的一種簡單方法是顯示該字符串的生產規則。

Answer 2

這裏的一個重要細節是，語法不要接受字符串;他們生成字符串。文法是語言的描述，提供了生成語言中包含的所有可能字符串的方法。爲了判斷語言中是否包含特定的字符串，可以使用識別器，某種自動機處理給定的字符串，並說「是」或「否」。

A context-free grammar（CFG）是一種語法，其中（如您所述）每個產品的格式爲A → w，其中A是非終結符，w是終端和非終結符的字符串。非正式地說，CFG是一種語法，任何非終結者都可以在任何時候擴展到任何生產。語法的語言是可以從開始符號導出的一組終端字符串。

A context-sensitive grammar（CSG）是一種語法，其中每個產品的形式爲wAx → wyx，其中w和x是終端和非終端的字符串，y也是終端的字符串。換句話說，這些作品給出的規則是「如果你在給定的上下文看到A ，你可以用字符串y代替A.」不幸的是，這些語法被稱爲「上下文敏感語法」，因爲它意味着「上下文無關」和「上下文敏感」不是相反的，並且這意味着有某些類型的語法可以採用很多上下文信息，但沒有正式被認爲是上下文敏感的。

要確定字符串是否包含在CFG或CSG中，有許多方法。首先，你可以爲給定的語法構建一個識別器。對於CFG，pushdown automaton（PDA）是一種精確接受上下文無關語言的自動機類型，並且將任何CFG轉換爲PDA都有一個簡單的構造。對於上下文敏感的語法，您要使用的自動機被稱爲（LBA）。

但是，如果天真地對待這些方法，這些方法效率不高。爲了確定字符串是否包含在CFG的語言中，有更高效的算法。例如，許多語法可以爲它們構建LL(k)或LR(k)解析器，這允許您（線性時間）決定語法中是否包含字符串。所有語法都可以使用Earley parser進行分析，在O中可以確定語法中是否包含長度爲n的字符串（有趣的是，它可以解析O中任何明確的CFG，並且使用lookaheads可以解析O（n）時間內的任何LR（k）語法！）。如果你完全對「語法G所產生的語言中包含的字符串x」這個問題感興趣，那麼其中一種方法就非常出色。如果您想知道字符串x是如何生成的（通過查找），您可以調整這些方法以提供此信息。然而，一般來說，解析CSGs是PSPACE完整的，所以沒有已知的解析算法在最壞情況下運行多項式時間。但是，有些算法在實踐中傾向於快速運行。作者解析技巧：實用指南（見下文）已放在一起a fantastic page containing all sorts of parsing algorithms，其中包括解析上下文敏感語言。

如果您有興趣瞭解更多關於解析的知識，可以考慮查看Grune和Jacobs撰寫的優秀書籍「Parsing Techniques: A Practical Guide, Second Edition」，其中討論了用於確定字符串是否包含在語法中的各種解析算法，如果是這樣，它是如何由解析算法生成的。

希望這會有所幫助！

Answer 3

如前所述，語法不接受字符串，但它只是一種方法，用於生成您分析的語言的特定單詞。事實上，作爲形式語言理論中的生成規則的語法，而不是有限狀態自動機做你正在說的，特定字符串的識別。 特別是，您需要遞歸枚舉自動機來識別類型1語言（Chomsky層次中的上下文相關語言）。 只有特定語言的語法纔會授予您指定收集到CS語言字符串集合的所有字符串的屬性。 我希望我的解釋清楚。