📄 sec-conflict-tips.html
字号:
<HTML
><HEAD
><TITLE
>Conflict Tips</TITLE
><META
NAME="GENERATOR"
CONTENT="Modular DocBook HTML Stylesheet Version 1.74b"><LINK
REL="HOME"
TITLE="Happy User Guide"
HREF="happy.html"><LINK
REL="UP"
TITLE="Tips"
HREF="sec-tips.html"><LINK
REL="PREVIOUS"
TITLE="Finding Type Errors"
HREF="sec-finding-errors.html"><LINK
REL="NEXT"
TITLE="Using Happy with GHCi"
HREF="sec-happy-ghci.html"></HEAD
><BODY
CLASS="SECT1"
><DIV
CLASS="NAVHEADER"
><TABLE
SUMMARY="Header navigation table"
WIDTH="100%"
BORDER="0"
CELLPADDING="0"
CELLSPACING="0"
><TR
><TH
COLSPAN="3"
ALIGN="center"
>Happy User Guide</TH
></TR
><TR
><TD
WIDTH="10%"
ALIGN="left"
VALIGN="bottom"
><A
HREF="sec-finding-errors.html"
ACCESSKEY="P"
>Prev</A
></TD
><TD
WIDTH="80%"
ALIGN="center"
VALIGN="bottom"
>Chapter 6. Tips</TD
><TD
WIDTH="10%"
ALIGN="right"
VALIGN="bottom"
><A
HREF="sec-happy-ghci.html"
ACCESSKEY="N"
>Next</A
></TD
></TR
></TABLE
><HR
ALIGN="LEFT"
WIDTH="100%"></DIV
><DIV
CLASS="SECT1"
><H1
CLASS="SECT1"
><A
NAME="SEC-CONFLICT-TIPS"
>6.4. Conflict Tips</A
></H1
><P
>Conflicts arise from ambiguities in the grammar. That is,
some input sequences may possess more than one parse.
Shift/reduce conflicts are benign in the sense that they are
easily resolved (<SPAN
CLASS="APPLICATION"
>Happy</SPAN
> automatically selects the
shift action, as this is usually the intended one).
Reduce/reduce conflicts are more serious. A reduce/reduce
conflict implies that a certain sequence of tokens on the input
can represent more than one non-terminal, and the parser is
uncertain as to which reduction rule to use. It will select the
reduction rule uppermost in the grammar file, so if you really
must have a reduce/reduce conflict you can select which rule
will be used by putting it first in your grammar file.</P
><P
>It is usually possible to remove conflicts from the
grammar, but sometimes this is at the expense of clarity and
simplicity. Here is a cut-down example from the grammar of
Haskell (1.2):</P
><TABLE
BORDER="0"
BGCOLOR="#E0E0E0"
WIDTH="100%"
><TR
><TD
><PRE
CLASS="PROGRAMLISTING"
>exp : exp op exp0
| exp0
exp0 : if exp then exp else exp
...
| atom
atom : var
| integer
| '(' exp ')'
...</PRE
></TD
></TR
></TABLE
><P
>This grammar has a shift/reduce conflict, due to the
following ambiguity. In an input such as</P
><TABLE
BORDER="0"
BGCOLOR="#E0E0E0"
WIDTH="100%"
><TR
><TD
><PRE
CLASS="PROGRAMLISTING"
>if 1 then 2 else 3 + 4</PRE
></TD
></TR
></TABLE
><P
>the grammar doesn't specify whether the parse should be</P
><TABLE
BORDER="0"
BGCOLOR="#E0E0E0"
WIDTH="100%"
><TR
><TD
><PRE
CLASS="PROGRAMLISTING"
>if 1 then 2 else (3 + 4)</PRE
></TD
></TR
></TABLE
><P
>or</P
><TABLE
BORDER="0"
BGCOLOR="#E0E0E0"
WIDTH="100%"
><TR
><TD
><PRE
CLASS="PROGRAMLISTING"
>(if 1 then 2 else 3) + 4</PRE
></TD
></TR
></TABLE
><P
>and the ambiguity shows up as a shift/reduce conflict on
reading the 'op' symbol. In this case, the first parse is the
intended one (the 'longest parse' rule), which corresponds to
the shift action. Removing this conflict relies on noticing
that the expression on the left-hand side of an infix operator
can't be an <TT
CLASS="LITERAL"
>exp0</TT
> (the grammar previously said
otherwise, but since the conflict was resolved as shift, this
parse was not allowed). We can reformulate the
<TT
CLASS="LITERAL"
>exp</TT
> rule as:</P
><TABLE
BORDER="0"
BGCOLOR="#E0E0E0"
WIDTH="100%"
><TR
><TD
><PRE
CLASS="PROGRAMLISTING"
>exp : atom op exp
| exp0</PRE
></TD
></TR
></TABLE
><P
>and this removes the conflict, but at the expense of some
stack space while parsing (we turned a left-recursion into a
right-recursion). There are alternatives using left-recursion,
but they all involve adding extra states to the parser, so most
programmers will prefer to keep the conflict in favour of a
clearer and more efficient parser.</P
><DIV
CLASS="SECT2"
><H2
CLASS="SECT2"
><A
NAME="SEC-LALR"
>6.4.1. LALR(1) parsers</A
></H2
><P
>There are three basic ways to build a shift-reduce
parser. Full LR(1) (the `L' is the direction in which the
input is scanned, the `R' is the way in which the parse is
built, and the `1' is the number of tokens of lookahead)
generates a parser with many states, and is therefore large
and slow. SLR(1) (simple LR(1)) is a cut-down version of
LR(1) which generates parsers with roughly one-tenth as many
states, but lacks the power to parse many grammars (it finds
conflicts in grammars which have none under LR(1)). </P
><P
>LALR(1) (look-ahead LR(1)), the method used by
<SPAN
CLASS="APPLICATION"
>Happy</SPAN
> and
<SPAN
CLASS="APPLICATION"
>yacc</SPAN
>, is tradeoff between the two.
An LALR(1) parser has the same number of states as an SLR(1)
parser, but it uses a more complex method to calculate the
lookahead tokens that are valid at each point, and resolves
many of the conflicts that SLR(1) finds. However, there may
still be conflicts in an LALR(1) parser that wouldn't be there
with full LR(1).</P
></DIV
></DIV
><DIV
CLASS="NAVFOOTER"
><HR
ALIGN="LEFT"
WIDTH="100%"><TABLE
SUMMARY="Footer navigation table"
WIDTH="100%"
BORDER="0"
CELLPADDING="0"
CELLSPACING="0"
><TR
><TD
WIDTH="33%"
ALIGN="left"
VALIGN="top"
><A
HREF="sec-finding-errors.html"
ACCESSKEY="P"
>Prev</A
></TD
><TD
WIDTH="34%"
ALIGN="center"
VALIGN="top"
><A
HREF="happy.html"
ACCESSKEY="H"
>Home</A
></TD
><TD
WIDTH="33%"
ALIGN="right"
VALIGN="top"
><A
HREF="sec-happy-ghci.html"
ACCESSKEY="N"
>Next</A
></TD
></TR
><TR
><TD
WIDTH="33%"
ALIGN="left"
VALIGN="top"
>Finding Type Errors</TD
><TD
WIDTH="34%"
ALIGN="center"
VALIGN="top"
><A
HREF="sec-tips.html"
ACCESSKEY="U"
>Up</A
></TD
><TD
WIDTH="33%"
ALIGN="right"
VALIGN="top"
>Using Happy with <SPAN
CLASS="APPLICATION"
>GHCi</SPAN
></TD
></TR
></TABLE
></DIV
></BODY
></HTML
>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -