在計算理論（TOC）中，語法和產生式是什麼意思？

讓我們瞭解一下計算理論 (TOC) 中語法的概念。

語法介紹

在字母表∑上的語言是由∑中字串組成的集合。

語法是用於定義語言的一組規則。簡而言之，它是語言中字串的結構。

為了描述一種語言的語法，需要兩個字母表（符號）集合。這些解釋如下：

• 終結符是從中構成語言中所有字串的符號——生成語言的“給定”字母表的符號。這些通常是小寫字母。

• 非終結符是用於定義語法替換規則（在產生式規則中）的“臨時”符號（與終結符不相交）。在產生式成功生成語言的有效字串之前，必須將所有這些替換為終結符。這些通常是大寫字母。

產生式

此外，語言L（在字母表∑上）的語法包含如下形式的一組語法規則（產生式）：

α → β，

其中α，β是從終結符（∑）和非終結符集合中取出的符號字串。

語法規則α → β可以用以下幾種方式閱讀：

• “用β替換α”，

• “α產生β”，

• “α重寫為β”，

• “α歸約為β”。

語法的形式化定義

考慮以下示例：

如果∑ = {a，b}並且S是一個非終結符，則規則S → aS，S → ∧是語言L的產生式的示例。

現在我們準備給出語法的形式化定義，如下所示：

• 稱為終結符的符號字母表T。這與結果語言的字母表相同。

• 稱為非終結符的語法符號字母表N，用於產生式規則。

• 一個特定的非終結符，稱為起始符號。它通常是S。

• 形式為α → β的有限產生式集合，其中α和β是字母表N∪T上的字串。

Bhanu Priya

更新於：2021年6月15日

3K+ 瀏覽量

啟動你的職業生涯

完成課程獲得認證

開始學習