Browse Prior Art Database

Method of Resolving LL(l) Parse Table Conflicts

IP.com Disclosure Number: IPCOM000115311D
Original Publication Date: 1995-Apr-01
Included in the Prior Art Database: 2005-Mar-30
Document File: 2 page(s) / 104K

Publishing Venue

IBM

Related People

Feriozi, DT: AUTHOR

Abstract

Described is a conflict resolution method for LL languages, as used by computer developers. The method resolves conflicts which occur in the LL(1) parse table when there are two different productions for the same parse table entry.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 50% of the total text.

Method of Resolving LL(l) Parse Table Conflicts

      Described is a conflict resolution method for LL languages, as
used by computer developers.  The method resolves conflicts which
occur in the LL(1) parse table when there are two different
productions for the same parse table entry.

      In prior art, there were only two viable choices for parsing
LL(2) languages, such as the C programming language.  One choice was
hand coding the parser.  This was both tedious and difficult to
modify.  The other choice was to use a bottom-up parser generator,
such as the UNIX tool YACC.  Top-down parsing was generally
considered to be preferable to bottom-up methods in all respects
except one.  That is that the bottom-up methods could handle a larger
class of grammars than the equivalent top-down method using the same
amount of lookahead.

      The described concept provides an efficient, automated top-down
parsing of strong LL(2) languages, like C, by using a LL(1)+ parsing
method.  This method requires the preconstruction of a conflict
resolution table.  While this conflict resolution method is primarily
targeted to building tables for LL(1)+ use, it may be applicable to
other parsing applications.

      An LL(1) parse table is first constructed from predict sets
that are taken from the FIRST and FOLLOW sets of the symbols in a
grammar.  The FIRST set for a symbol is the set of all terminal
symbols that may begin a sentential form that can be derived from
that symbol.  The FOLLOW set is the set of all terminals that can
follow the symbol in a valid sentence in the language.  The parse
table maps a given non-terminal symbol and a given terminal symbol,
called the lookahead token, to a unique production in the language.
If a unique predict set cannot be constructed for the grammar, it is
said not to be an LL(1) grammar.  The LL(1) parsing method cannot be
used to parse sentences in the language.

      A conflict occurs in the LL(1) parse table when there are two
different productions for the same parse table entry.  In this case,
the LL(1) method is not able to predict which production to use,
given the current non-terminal symbol and the current lookahead
terminal symbol.  If the language in question is LL(2), the next
lookahead symbol will enable resolution of the conflict.

      The method of determining how to resolve the LL(1) conflict is
to recursively search both conflicting productions for the terminal
symbol that caused the conflict.  Then the following symbol is used
to determine when each production should be used.  In general, the
search algorithm proceeds as follows:
  1.  Look for the conflicting terminal on the right side of the
       production.
  2.  If it is found, append the following symbol to the conflict
       resolution list and return.
  3.  If is not found, let lhs equal the first grammar symbol on the
       right hand side of the production.
  4.  For eac...