Visualize Ambiguities

XT -- A Bundle of Program Transformation Tools

Name

visamb -- display the ambiguities in a parse tree represented in AsFix2?

Synopsis

Description

The SDF2 implementation caters for arbitrary context-free grammars. That is, even for ambiguous grammars the parser will produce a parse trees containing a concise encoding of allpossible parses. Ambiguities are represented by means of amb nodes that contain a list of possible parse trees at that point. For most applications, however, it is desirable to develop unambiguous grammars. To aid the grammar writer in detecting and solving the ambiguities, the visamb tool extracts the ambiguities from a parse tree and displays them in a readable format.

Ambiguities are displayed by printing the non-terminals of the nodes of the parse trees in the ambiguities. For instance, consider the syntax definition

  definition
  module Main
  exports
    sorts Exp
    lexical syntax
      [\ \t\n] -> LAYOUT
    context-free syntax
      "id"    -> Exp
      Exp Exp -> Exp

From this syntax definition an SGLR parse table can be generated:

  sdf2table -i Exp.sdf -o Exp.tbl

The ambiguities of the phrase id id id can be shown with:

  echo "id id id" | sglr -2 -p Exp.tbl | visamb

the output of this command is:

  # ambiguities = 1
  + * id id id
    <Exp-CF>
      <Exp-CF>
        <Exp-CF>
          id
        <LAYOUT?-CF>
          <LAYOUT-CF>

        <Exp-CF>
          id
      <LAYOUT?-CF>
        <LAYOUT-CF>

      <Exp-CF>
        id
    <Exp-CF>
      <Exp-CF>
        id
      <LAYOUT?-CF>
        <LAYOUT-CF>

      <Exp-CF>
        <Exp-CF>
          id
        <LAYOUT?-CF>
          <LAYOUT-CF>

        <Exp-CF>
          id

Only the inner ambiguities are displayed, i.e., if a phrase and one of its sub-phrases are ambiguous, only the ambiguities of the sub-phrase is displayed.

Tools.VisualizeAmbiguities moved from Tools.visambGT on 17 Feb 2004 - 11:40 by MartinBravenboer - put it back