NAME

Parse::Eyapp - Extensions for Parse::Yapp

SYNOPSIS

use Parse::Eyapp;
use Parse::Eyapp::Treeregexp;

sub TERMINAL::info {
  $_[0]{attr}
}

my $grammar = q{
  %right  '='     # Lowest precedence
  %left   '-' '+' # + and - have more precedence than = Disambiguate a-b-c as (a-b)-c
  %left   '*' '/' # * and / have more precedence than + Disambiguate a/b/c as (a/b)/c
  %left   NEG     # Disambiguate -a-b as (-a)-b and not as -(a-b)
  %tree           # Let us build an abstract syntax tree ...

  %%
  line:
      exp <%name EXPRESION_LIST + ';'>
        { $_[1] } /* list of expressions separated by ';' */
  ;

  /* The %name directive defines the name of the class to which the node being built belongs */
  exp:
      %name NUM
      NUM
    | %name VAR
      VAR
    | %name ASSIGN
      VAR '=' exp
    | %name PLUS
      exp '+' exp
    | %name MINUS
      exp '-' exp
    | %name TIMES
      exp '*' exp
    | %name DIV
      exp '/' exp
    | %name UMINUS
      '-' exp %prec NEG
    | '(' exp ')'
        { $_[2] }  /* Let us simplify a bit the tree */
  ;

  %%
  sub _Error { die "Syntax error near ".($_[0]->YYCurval?$_[0]->YYCurval:"end of file")."\n" }

  sub _Lexer {
    my($parser)=shift; # The parser object

    for ($parser->YYData->{INPUT}) { # Topicalize
      m{\G\s+}gc;
      $_ eq '' and return('',undef);
      m{\G([0-9]+(?:\.[0-9]+)?)}gc and return('NUM',$1);
      m{\G([A-Za-z][A-Za-z0-9_]*)}gc and return('VAR',$1);
      m{\G(.)}gcs and return($1,$1);
    }
    return('',undef);
  }

  sub Run {
      my($self)=shift;
      $self->YYParse( yylex => \&_Lexer, yyerror => \&_Error, );
  }
}; # end grammar

our (@all, $uminus);

Parse::Eyapp->new_grammar( # Create the parser package/class
  input=>$grammar,
  classname=>'Calc', # The name of the package containing the parser
  firstline=>7       # String $grammar starts at line 7 (for error diagnostics)
);
my $parser = Calc->new();                # Create a parser
$parser->YYData->{INPUT} = "2*-3+b*0;--2\n"; # Set the input
my $t = $parser->Run;                    # Parse it!
local $Parse::Eyapp::Node::INDENT=2;
print "Syntax Tree:",$t->str;

# Let us transform the tree. Define the tree-regular expressions ..
my $p = Parse::Eyapp::Treeregexp->new( STRING => q{
    { #  Example of support code
      my %Op = (PLUS=>'+', MINUS => '-', TIMES=>'*', DIV => '/');
    }
    constantfold: /TIMES|PLUS|DIV|MINUS/:bin(NUM($x), NUM($y))
      => {
        my $op = $Op{ref($bin)};
        $x->{attr} = eval  "$x->{attr} $op $y->{attr}";
        $_[0] = $NUM[0];
      }
    uminus: UMINUS(NUM($x)) => { $x->{attr} = -$x->{attr}; $_[0] = $NUM }
    zero_times_whatever: TIMES(NUM($x), .) and { $x->{attr} == 0 } => { $_[0] = $NUM }
    whatever_times_zero: TIMES(., NUM($x)) and { $x->{attr} == 0 } => { $_[0] = $NUM }
  },
  OUTPUTFILE=> 'main.pm'
);
$p->generate(); # Create the tranformations

$t->s($uminus); # Transform UMINUS nodes
$t->s(@all);    # constant folding and mult. by zero

local $Parse::Eyapp::Node::INDENT=0;
print "\nSyntax Tree after transformations:\n",$t->str,"\n";

INTRODUCTION

Parse::Eyapp (Extended yapp) is a collection of modules that extends Francois Desarmenien Parse::Yapp 1.05. Eyapp extends yacc/yapp syntax with functionalities like named attributes, EBNF-like expressions, modifiable default action, grammar reusability, automatic syntax tree building, semi-automatic abstract syntax tree building, translation schemes, tree regular expressions, tree transformations, scope analysis support, directed acyclic graphs and a few more.

THE DOCUMENTATION OF Parse::Eyapp

The documentation is distributed among several files:

To get familiar with eyapp read Parse::Eyapp::eyappintro and Parse::Eyapp::debuggingtut. It assumes a reader familiar with parsing techniques. Familiarity with yacc or yapp, RecDescent, ANTLR or similar tools will help but it is not indispensable.
The document Parse::Eyapp::defaultactionsintro describes the use of default actions and how to deal with grammar reuse and factorization.
The document Parse::Eyapp::eyapplanguageref describes the Eyapp language.
The document Parse::Eyapp::translationschemestut describes the use of Translation Schemes inside the Eyapp language.
The Treeregexp language is described in Parse::Eyapp::Treeregexp. Treeregexp is a language to describe transformations of abstract syntax trees.
Read Parse::Eyapp::Scope to know about the functionalities provided for Scope Analysis.
A set of basic miscellaneous support sunctions are described in Parse::Eyapp::Base. Several of these functions are related to the dynamic use of methods and subroutines.
Don't forget to read the section "BUGS AND LIMITATIONS"

The examples used in this document can be found in the directory examples/Eyapp accompanying this distribution.

THE EYAPP LANGUAGE

See Parse::Eyapp::eyapplanguageref for an introduction to the Eyapp language

`Parse::Eyapp` METHODS

A Parse::Eyapp object holds the information about the Eyapp input grammar: parsing tables, conflicts, semantic actions, etc.

Parse::Eyapp->new_grammar

To translate an Eyapp grammar you must use either the eyapp script or call the class constructor new_grammar. The Parse::Eyapp method Parse::Eyapp->new_grammar(input=>$grammar) creates a package containing the code that implements a LALR parser for the input grammar:

my $p = Parse::Eyapp->new_grammar(
  input=>$translationscheme,
  classname=>'Grammar',
  firstline => 6,
  outputfile => 'main'
);
die $p->Warnings if $p->Warnings;
my $new_parser_for_grammar = Grammar->new();

The method returns a Parse::Eyapp object.

You can check the object to see if there were problems during the construction of the parser for your grammar:

die $p->qtables() if $p->Warnings;

The method Warnings returns the warnings produced during the parsing. The absence of warnings indicates the correctness of the input program.

The call to Parse::Eyapp->new_grammar generates a class/package containing the parser for your input grammar. Such package lives in the namespace determined by the classname argument of new_grammar. To create a parser for the grammar you call the constructor new of the just created class:

my $new_parser_for_grammar = Grammar->new();

The meaning of the arguments of Parse::Eyapp->new_grammar is:

- input: The string containing the input
- classname: The name of the package that will held the code for the LALR parser. The package of the caller will be used as default if none is specified.
- firstline: For error diagnostics. The line where the definition of the Eyapp grammar starts.
- linenumbers: Include/not include # line directives in the generated code
- outputfile: If defined the generated code fill be dumped in the specified filename (with extension .pm) and the LALR information ambigueties and conflicts) in the specified filename with extension .output.

$eyapp->qtables

Returns a string containing information on warnings, ambiguities, conflicts, rules and the generated DFA tables. Is the same information in file.output when using the command eyapp -v file.eyp.

my $p = Parse::Eyapp->new_grammar(
  input=>$eyappprogram,
  classname=>'SimpleC',
  outputfile => 'SimpleC.pm',
  firstline=>12,
);

print $p->qtables() if $p->Warnings;

$eyapp->outputtables

It receives two arguments

$eyapp->outputtables($path, $base)

Similar to qtables but prints the information on warnings, conflicts and rules to the specified $path/$base.

$eyapp->Warnings

Returns the warnings resulting from compiling the grammar:

my $p = Parse::Eyapp->new_grammar(
  input=>$translationscheme,
  classname=>'main',
  firstline => 6,
  outputfile => 'main'
);
die $p->Warnings if $p->Warnings;

Returns the empty string if there were no conflicts.

$eyapp->ShowDfa

Returns a string with the information about the LALR generated DFA.

$eyapp->Summary

Returns a string with summary information about the compilation of the grammar. No arguments.

$eyapp->Conflicts

Returns a string with summary information about the conflicts that arised when compiling the grammar. No arguments.

$eyapp->DfaTable

Returns a string with the parsing tables

METHODS AVAILABLE IN THE GENERATED `CLASS`

See the documentation for Parse::Eyapp::Driver

`Parse::Eyapp::Parse` OBJECTS

The parser for the Eyapp language was written and generated using Parse::Eyapp and the eyapp compiler (actually the first version was bootstrapped using the yapp compiler). The Eyapp program parsing the Eyapp language is in the file Parse/Eyapp/Parse.yp in the Parse::Eyapp distribution. Therefore Parse::Eyapp::Parse objects have all the methods in Parse::Eyapp::Driver.

A Parse::Eyapp::Parse is nothing but a particular kind of Parse::Eyapp parser: the one that parses Eyapp grammars.

TRANSLATION SCHEMES AND THE `%metatree` DIRECTIVE

See the documentation for Parse::Eyapp::translationschemestut

THE TREEREGEXP LANGUAGE

See the documentation for Parse::Eyapp::Treeregexp

MANIPULATING ABSTRACT SYNTAX TREES

See the documentation for Parse::Eyapp::Node

TREE TRANSFORMATION OBJECTS

See the documentation for Parse::Eyapp::YATW

COMPILING WITH `eyapp` AND `treereg`

A Treeregexp program can be isolated in a file an compiled with the program treereg. The default extension is .trg. See the following example:

pl@nereida:~/src/perl/YappWithDefaultAction/examples/Eyapp$ cat -n Shift.trg
   1  # File: Shift.trg
   2  {
   3    sub log2 {
   4      my $n = shift;
   5      return log($n)/log(2);
   6    }
   7
   8    my $power;
   9  }
  10  mult2shift: TIMES($e, NUM($m))
  11    and { $power = log2($m->{attr}); (1 << $power) == $m->{attr} } => {
  12      $_[0]->delete(1);
  13      $_[0]->{shift} = $power;
  14      $_[0]->type('SHIFTLEFT');
  15    }

Note that auxiliary support code can be inserted at any point between transformations (lines 2-9). The code will be inserted (without the defining curly brackets) at that point. Note also that the lexical variable $power is visible inside the definition of the mult2shift transformation.

A treeregexp like $e matches any node (line 10). A reference to the node is saved in the lexical variable $e. The scope of the variable $e is the current tree transformation, i.e. mult2shift. Such kind of treeregexps are called scalar treeregexps.

The call to the delete method at line 12 deletes the second child of the node being visited (i.e. NUM($m)).

The call to type at line 14 retypes the node as a SHIFTLEFT node.

The program is compiled using the script treereg:

pl@nereida:~/src/perl/YappWithDefaultAction/examples/Eyapp$ eyapp Rule5
pl@nereida:~/src/perl/YappWithDefaultAction/examples/Eyapp$ treereg Shift
pl@nereida:~/src/perl/YappWithDefaultAction/examples/Eyapp$ ls -ltr | tail -2
-rw-r--r-- 1 pl users 6439 2008-09-02 08:59 Rule5.pm
-rw-r--r-- 1 pl users 1424 2008-09-02 08:59 Shift.pm

The Grammar Rule5.yp is similar to the one in the "SYNOPSIS" section. Module Rule5.pm contains the parser. The module Shift.pm contains the code implementing the tree transformations.

The client program follows:

pl@nereida:~/src/perl/YappWithDefaultAction/examples/Eyapp$ cat -n useruleandshift.pl
   1  #!/usr/bin/perl -w
   2  use strict;
   3  use Rule5;
   4  use Parse::Eyapp::Base qw(insert_function);
   5  use Shift;
   6
   7  sub SHIFTLEFT::info { $_[0]{shift} }
   8  insert_function('TERMINAL::info', \&TERMINAL::attr);
   9
  10  my $parser = new Rule5();
  11  my $t = $parser->Run;
  12  print "***********\n",$t->str,"\n";
  13  $t->s(@Shift::all);
  14  print "***********\n",$t->str,"\n";

Lines 7 and 8 provide the node classes TERMINAL and SHIFTLEFT of info methods to be used during the calls to the str method (lines 12 and 14).

Multiplications by a power of two are substituted by the corresponding shifts:

pl@nereida:~/src/perl/YappWithDefaultAction/examples/Eyapp$ useruleandshift.pl
a=b*8
***********
ASSIGN(TERMINAL[a],TIMES(VAR(TERMINAL[b]),NUM(TERMINAL[8])))
***********
ASSIGN(TERMINAL[a],SHIFTLEFT[3](VAR(TERMINAL[b])))

Compiling: More Options

See files Rule9.yp, Transform4.trg and foldand0rule9_4.pl in the examples directory for a more detailed vision of this example. File Rule9.yp is very much like the grammar in the "SYNOPSIS" example. To compile the grammar Rule9.yp and the treeregexp file Transform4.trg use the commands:

eyapp -m 'Calc' Rule9.yp

That will produce a file Calc.pm containing a package Calc that implements the LALR parser. Then the command:

treereg -o T.pm -p 'R::' -m T Transform4

produces a file T.pm containing a package T that implements the tree transformation program. The -p option announces that node classes are prefixed by 'R::'.

With such parameters the client program uses the generated modules as follows:

nereida:~/src/perl/YappWithDefaultAction/examples> cat -n foldand0rule9_4.pl
 1  #!/usr/bin/perl -w
 2  # File: foldand0rule9_4.pl. Compile it with
 3  #          eyapp -m 'Calc' Rule9.yp; treereg -o T.pm -p 'R::' -m T Transform4
 4  use strict;
 5  use Calc;
 6  use T;
 7
 8  sub R::TERMINAL::info { $_[0]{attr} }
 9  my $parser = new Calc(yyprefix => "R::");
10  my $t = $parser->YYParse( yylex => \&Calc::Lexer, yyerror => \&Calc::Error);
11  print "\n***** Before ******\n";
12  print $t->str."\n";
13  $t->s(@T::all);
14  print "\n***** After ******\n";
15  print $t->str."\n";

running the program produces the following output:

nereida:~/src/perl/YappWithDefaultAction/examples> foldand0rule9_4.pl
2*3

***** Before ******
R::TIMES(R::NUM(R::TERMINAL[2]),R::TERMINAL[*],R::NUM(R::TERMINAL[3]))

***** After ******
R::NUM(R::TERMINAL[6])

Parse::Eyapp::Scope: SUPPORT FOR SCOPE ANALYSIS

See the documentation for Parse::Eyapp::Scope

MISCELLANEOUS SUPPORT FUNCTIONS IN Parse::Eyapp::Base

See the documentation in Parse::Eyapp::Base

ENVIRONMENT

Remember to set the environment variable PERL5LIB if you decide to install Parse::Eyapp at a location other than the standard. For example, on a bash or sh:

export PERL5LIB=/home/user/wherever_it_is/lib/:$PERL5LIB

on a csh or tcsh

setenv PERL5LIB /home/user/wherever_it_is/lib/:$PERL5LIB

Be sure the scripts eyapp and treereg are in the execution PATH.

DEPENDENCIES

This distribution depends on the following modules:

It seems that List::Util is in the core of Perl distributions since version 5.73:

> perl -MModule::CoreList -e 'print Module::CoreList->first_release("List::Util")'
5.007003

and Data::Dumper is also in the core since 5.5:

> perl -MModule::CoreList -e 'print Module::CoreList->first_release("Data::Dumper")'
5.005

and Pod::Usage is also in the core since 5.6:

> perl -MModule::CoreList -e 'print Module::CoreList->first_release("Pod::Usage")'
5.006

I also recommend the following modules:

The dependence on Test::Warn, Test::Pod and Test::Exception is merely for the execution of tests. If the modules aren't installed the tests depending on them will be skipped.

INSTALLATION

To install it, follow the traditional mantra:

perl Makefile.PL
make
make test
make install

Also:

Make a local copy of the examples/ directory in this distribution
Probably it will be also a good idea to make a copy of the tests in the t/ directory. They also illustrate the use of Eyapp

BUGS AND LIMITATIONS

The way Parse::Eyapp parses Perl code is verbatim the way it does Parse::Yapp 1.05. Quoting Francois Desarmenien Parse::Yapp documentation:

"Be aware that matching braces in Perl is much more difficult than in C: inside strings they don't need to match. While in C it is very easy to detect the beginning of a string construct, or a single character, it is much more difficult in Perl, as there are so many ways of writing such literals. So there is no check for that today. If you need a brace in a double-quoted string, just quote it (\{ or \}). For single-quoted strings, you will need to make a comment matching it in th right order. Sorry for the inconvenience.
```
{
    "{ My string block }".
    "\{ My other string block \}".
    qq/ My unmatched brace \} /.
    # Force the match: {
    q/ for my closing brace } /
    q/ My opening brace { /
    # must be closed: }
}
```
All of these constructs should work."

Alternative exact solutions were tried but resulted in much slower code. Therefore, until something faster is found, I rather prefer for Parse::Eyapp to live with this limitation.

The same limitation may appear inside header code (code between %{ and %})

REFERENCES

The classic Dragon's book Compilers: Principles, Techniques, and Tools by Alfred V. Aho, Ravi Sethi and Jeffrey D. Ullman (Addison-Wesley 1986)

AUTHOR

Casiano Rodriguez-Leon (casiano@ull.es)

ACKNOWLEDGMENTS

This work has been supported by CEE (FEDER) and the Spanish Ministry of Educacion y Ciencia through Plan Nacional I+D+I number TIN2005-08818-C04-04 (ULL::OPLINK project http://www.oplink.ull.es/). Support from Gobierno de Canarias was through GC02210601 (Grupos Consolidados). The University of La Laguna has also supported my work in many ways and for many years.

A large percentage of code is verbatim taken from Parse::Yapp 1.05. The author of Parse::Yapp is Francois Desarmenien.

I wish to thank Francois Desarmenien for his Parse::Yapp module, to my students at La Laguna and to the Perl Community. Special thanks to my family and Larry Wall.

LICENCE AND COPYRIGHT

These modules are free software; you can redistribute it and/or modify it under the same terms as Perl itself. See perlartistic.

This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

To install Parse::Eyapp, copy and paste the appropriate command in to your terminal.

cpanm

cpanm Parse::Eyapp

CPAN shell

perl -MCPAN -e shell
install Parse::Eyapp

For more information on module installation, please visit the detailed CPAN module installation guide.

	Global
`s`	Focus search bar
`?`	Bring up this help dialog

	GitHub
`g` `p`	Go to pull requests
`g` `i`	go to github issues (only if github is preferred repository)

	POD
`g` `a`	Go to author
`g` `c`	Go to changes
`g` `i`	Go to issues
`g` `d`	Go to dist
`g` `r`	Go to repository/SCM
`g` `s`	Go to source
`g` `b`	Go to file browse

	Search terms
module: (e.g. module:Plugin)
distribution: (e.g. distribution:Dancer auth)
author: (e.g. author:SONGMU Redis)
version: (e.g. version:1.00)