Search CTRL + K

Left-to-right and Leftmost derivation Parsing (LL Parsing)

LL 分析(Left-to-right and Leftmost derivation Parsing) 是处理 上下文无关语法自顶向下分析 算法,它从左往右扫描输入,并对句型执行 最左推导 得到语法树。

能够被 LL 分析形式语法 被称为 LL 文法。

使用 k 个词法单元(token)向前探查,而不需要回溯的 LL 分析LL(k) 分析,对应的 形式文法 称为 LL(k) 文法,对应的 形式语言 称为 LL(k) 语言。其中,较为严格的 LL(1) 文法因为很容易构造,且通常能满足需求,被大多数编程语言采用。

其中,LL(k+1) 语言包含 LL(k) 语言(k>=0):


In computer science, an LL parser (Left-to-right, leftmost derivation) is a top-down parser for a restricted context-free language. It parses the input from Left to right, performing Leftmost derivation of the sentence.

An LL parser is called an LL(k) parser if it uses k tokens of lookahead when parsing a sentence. A grammar is called an LL(k) grammar if an LL(k) parser can be constructed from it. A formal language is called an LL(k) language if it has an LL(k) grammar. The set of LL(k) languages is properly contained in that of LL(k+1) languages, for each k ≥ 0.[1] A corollary of this is that not all context-free languages can be recognized by an LL(k) parser.[1]

  1. ↩︎