CYK算法
CYK算法（，縮寫為CYK algorithm）是由約翰·科克，Younger和共同研究出来大约发表于1965年的一个算法，它是一个用来判定任意给定的字符串~w \in \Sigma^ 是否属于一个上下文无关文法的算法。普通的回溯法（backtracking）在最坏的情况下需要指数时间才能解决这样的问题，而CYK算法只需要多项式时间就够了（~O(n^3) ， n 为字符串 w 的长度）。CYK算法采用了动态规划的思想。 对于一个任意给定…
标签：#分析演算法
共 11 篇文章
LALR语法分析器
在计算机科学中，LALR分析器是一种的简化形式。它可以对上下无关文法进行语法分析。LALR即“Look-Ahead LR”。其中，Look-Ahead为“向前看”，L代表对输入进行从左到右的检查，R代表反向构造出最右推导序列。 LALR分析器可以根据一种程序设计语言的正式语法的而对一段文本程序输入进行语法分析，从而在语法层面上判断输入程序是否合法。 实际应用中的LALR分析器并不是由人手工写成的，而是由类似于yacc和GNU Bison…
递归下降解析器
在计算机科学中，递归下降解析器是一种，由一组相互递归的程序（或等价的非递归程序）构建而成，其中每个程序都实现了文法中的一个非终结符。因此，这些程序的结构密切反映了它所识别的文法结构。 预测性解析器是一种不需要回溯的递归下降解析器。预测性解析只适用于 LL(k) 文法。这是一种上下文无关文法。这种文法允许递归下降解析器仅通过检测之后 k 个标记决定当前标记（token）所使用的。LL(k) 文法由此排除了所有包含和左递归的文法。虽然任何一…
內部外部演算法
內部外部演算法（英語：inside-outside algorithm）是一種重新檢驗隨機上下文無關文法生成機率的方式，由詹姆斯·K·貝克於1979年提出，是一個一般化的向前向後演算法，用來作為隨機上下文無關文法其隱馬爾可夫模型的屬性評估。這種演算法是用來計算某種期望值，舉例來說，可以用來成為最大期望算法（一種無監督的學習演算法）的一部分。 參考資料 J. Baker (1979): Trainable grammars for spe…
语法分析
在计算机科学和语言学中，语法分析（，也叫 ）是根据某种给定的形式文法对由单词序列（如英语单词序列）构成的输入文本进行分析并确定其语法结构的一种过程。 语法分析器（parser）通常是作为编译器或解释器的组件出现的，它的作用是进行语法检查、并构建由输入的单词组成的数据结构（一般是语法分析树、抽象语法树等层次化的数据结构）。语法分析器通常使用一个独立的词法分析器从输入字符流中分离出一个个的“单词”，并将单词流作为其输入。实际开发中，语法分析…
LL剖析器
LL分析器是一种处理某些上下文无关文法的自顶向下分析器。因为它从左（Left）到右处理输入，再对句型执行最左推导出语法树（Left derivation，相对于LR分析器）。能以此方法分析的文法称为LL文法。 在解析句子时使用 k 个词法单元作向前探查的LL分析器被称为 \text{LL}(k) 解析器。若一个文法能构造出可以在不用回溯法进行回溯的情况下处理文法的分析器，则称该文法为 *LL(k) 文法。如果一个形式语言拥有 \text…
调度场算法
调度场算法（Shunting Yard Algorithm）是一个用于将中缀表达式转换为后缀表达式的经典算法，由艾兹格·迪杰斯特拉引入，因其操作类似于火车编组场而得名。 簡例 :输入：3+4 #将3入输出队列（每当输入一个数字时，直接进入输出队列） #将+号压入运算堆栈 #将4入输出队列 #输入结束，将操作符堆栈中剩余操作符入输出队列 #在本情况下只有+号 #输出 通过这个例子可以看出两条规则： 当读入一个数字时直接入输出队列 当输入结…
LR剖析器
LR剖析器是一種由下而上（bottom-up）的上下文無關語法剖析器。LR意指由左（Left）至右處理輸入字串，並以最右邊優先衍生（Right derivation）的推導順序（相對於LL剖析器）建構語法樹。能以此方式剖析的語法稱為LR語法。而在LR(k)這樣的名稱中，k代表的是剖析時所需前瞻符號（lookahead symbol）的數量，也就是除了目前處理到的輸入符號之外，還得再向右參照幾個符號之意；省略 （k）時即視為LR(1)，而…
左遞歸
在電腦科學裡面，左遞歸是一種遞歸的特殊狀況。 在上下文無關文法內裡的說法，若一個非终结符號（non-terminal）r有任何直接的文法規則或者透過多個文法規則，推導出的句型（sentential form）其中最左邊的符號 又會出現r，則我們說這個非终结符號r是左遞歸的。 使用類似的方式我們可以定義出某文法本身是左遞歸的。 定義 "一個文法是左遞歸的，若我們可以找出其中存在某非终结符號A，最終會推導出來的句型(sentential f…
編譯器編譯程式
一個編譯器編譯程式(compiler-compiler)或者編譯器產生程式(compiler generator)是一個幫助使用者根據某種語言或機器的規則來產生語法分析器，直譯器或者編譯器的工具。目前最早也是最常見的編譯器編譯程式是語法分析器產生程式(parser generator)這個形式，其輸入是一個程式語言的形式文法 (一般是用BNF表示)，然後產生出一些語法分析器的程式碼，作為這個語言編譯器的一部分。 理想的編譯器編譯程式，只…
剖析表
剖析表是剖析器(parser)的一部分，用來幫助剖析器作某些決定，並且告訴編譯器之後要怎樣處理輸入的符記(token)。 概觀 剖析表是一個告訴剖析器在特定狀態下，遇到特定輸入時需要作甚麼動作的一張表。一般可以視為是一個用表格表示的下推自動機，這裡的下推式自動機是根據要被剖析的語言其上下文無關語法而設計。 相關頁面 確定有限狀態自動機 LR剖析器 LL剖析器 編譯器 參考資料 * [https://web.archive.org/web…