In
formal language theory
In logic, mathematics, computer science, and linguistics, a formal language consists of words whose letters are taken from an alphabet and are well-formed according to a specific set of rules.
The alphabet of a formal language consists of sy ...
, the left corner of a
production rule in a
context-free grammar
In formal language theory, a context-free grammar (CFG) is a formal grammar whose production rules are of the form
:A\ \to\ \alpha
with A a ''single'' nonterminal symbol, and \alpha a string of terminals and/or nonterminals (\alpha can be ...
is the left-most symbol on the right side of the rule.
9.3 Using Left-corner Tables
Patrick Blackburn and Kristina Striegnitz, Natural Language Processing Techniques in Prolog
For example, in the rule ''A→Xα'', ''X'' is the left corner.
The left corner table associates to a symbol all possible left corners for that symbol, and the left corners of those symbols, etc.
Given the grammar
:S → VP
:S → NP VP
:VP → V NP
:NP → DET N
the left corner table is as follows.
Left corners are used to add bottom-up filtering to a top-down parser Top-down parsing in computer science is a parsing strategy where one first looks at the highest level of the parse tree and works down the parse tree by using the rewriting rules of a formal grammar. LL parsers are a type of parser that uses a top-d ...
, or top-down filtering to a bottom-up parser
Bottom-up may refer to:
* Bottom-up analysis, a fundamental analysis technique in accounting and finance
* Bottom-up parsing, a computer science strategy
* Bottom-up processing, in Pattern recognition (psychology)
* Bottom-up theories of galaxy fo ...
.
References
Parsing
{{Comp-sci-stub