左遞歸和編譯器編譯程式

快捷方式: 差异，相似，杰卡德相似系数，参考。

左遞歸和編譯器編譯程式之间的区别

左遞歸 vs. 編譯器編譯程式

在電腦科學裡面，左遞歸是一種遞歸的特殊狀況。 在上下文無關文法內裡的說法，，若一個非終端符號（non-terminal）r有任何直接的文法規則或者透過多個文法規則，推導出的句型（sentential form）其中最左邊的符號 又會出現r，則我們說這個非終端符號r是左遞歸的。 使用類似的方式我們可以定義出某文法本身是左遞歸的。. 一個編譯器編譯程式(compiler-compiler)或者編譯器產生程式(compiler generator)是一個幫助使用者根據某種語言或機器的規則來產生語法分析器，直譯器或者編譯器的工具。目前最早也是最常見的編譯器編譯程式是語法分析器產生程式(parser generator)這個形式，其輸入是一個程式語言的形式文法 (一般是用BNF表示)，然後產生出一些語法分析器的程式碼，作為這個語言編譯器的一部分。 理想的編譯器編譯程式，只要給予一個程式語言的完整描述以及目標的指令集架構，然後就能自動從中產生出合適的編譯器。實際上, 最先進的技術還沒有到達這麼複雜的地步，而大多數現有的編譯器產生程式都不能處理語意學或者目標架構的資訊部份。.

形式文法

在计算机科学中，形式语言是：某个字母表上，一些有限长字串的集合，而形式文法是描述这个集合的一种方法。形式文法之所以这样命名，是因为它与人类自然语言中的文法相似的缘故。 形式文法描述形式语言的基本想法是，从一个特殊的初始符号出发，不断的应用一些产生式规则，从而生成出一个字串的集合。产生式规则指定了某些符号组合如何被另外一些符号组合替换。举例来说，假设字母表只包含'a'和'b'两个字符，初始符号是'S'，我们应用下述规则： 于是我们可以通过把"S"重写为"aSb"（规则1），我们还可以继续应用这条规则把"aSb"重写为"aaSbb"。这个重写的过程不断重复，直到结果中只包含字母表中的字母为止。在例子中，我们可以得到S -> aSb -> aaSbb -> aababb这样的结果。由文法刻画的语言，包含了所有可以这样产生的字串，比如ba, abab, aababb, aaababbb等等。.

左遞歸和形式文法 · 形式文法和編譯器編譯程式 · 查看更多 »

語法分析器

在计算机科学和语言学中，语法分析（syntactic analysis，也叫 parsing）是根据某种给定的形式文法对由单词序列（如英语单词序列）构成的输入文本进行分析并确定其语法结构的一种过程。 语法分析器（parser）通常是作为编译器或解释器的组件出现的，它的作用是进行语法检查、并构建由输入的单词组成的数据结构（一般是语法分析树、抽象语法树等层次化的数据结构）。语法分析器通常使用一个独立的词法分析器从输入字符流中分离出一个个的“单词”，并将单词流作为其输入。实际开发中，语法分析器可以手工编写，也可以使用工具（半）自动生成。.

左遞歸和語法分析器 · 編譯器編譯程式和語法分析器 · 查看更多 »

GNU bison

GNU bison（Bison意为犎牛；而Yacc与意为牦牛的Yak同音）是一个自由软件，用于自动生成语法分析器程序，实际上可用于所有常见的操作系统。Bison把LALR形式的上下文无关文法描述转换为可做语法分析的C或C++程序。在新近版本中，Bison增加了对GLR语法分析算法的支持。 GNU bison基本兼容Yacc，并做了一些改进。它一般与flex一起使用。.

GNU bison和左遞歸 · GNU bison和編譯器編譯程式 · 查看更多 »

Yacc

yacc（Yet Another Compiler Compiler），是Unix/Linux上一个用来生成编译器的编译器（编译器代码生成器）。yacc生成的编译器主要是用C語言寫成的语法解析器（Parser），需要与词法解析器Lex一起使用，再把兩部份產生出來的C程序一併編譯。yacc本來只在Unix系統上才有，但現時已普遍移植往Windows及其他平台。 yacc的输入是巴科斯范式（BNF）表达的语法规则以及语法规约的处理代码，Yacc输出的是基于表驱动的编译器，包含输入的语法规约的处理代码部分。 yacc是开发编译器的一个有用的工具，采用LALR（1）语法分析方法。 yacc最初由AT&T的Steven C. Johnson为Unix操作系统开发，后来一些兼容的程序如Berkeley Yacc，GNU bison，MKS yacc和Abraxas yacc陆续出现。它们都在原先基础上做了少许改进或者增加，但是基本概念是相同的。 由于所产生的解析器需要词法分析器配合，因此Yacc经常和词法分析器的产生器——一般就是Lex——联合使用。IEEE POSIX P1003.2标准定义了Lex和Yacc的功能和需求。.

Yacc和左遞歸 · Yacc和編譯器編譯程式 · 查看更多 »