PGG - Parser Generator Generator for Functional Languages

by Taekyung Kim and Sungwoo Park

• Introduction
• Requirements
• How to use PGG
• Implementing Translation module
• Input-specification of PGG parser-generator
• Invoking PGG parser
• Examples

Introduction

While a parser-generator takes as input an input-specification to generate a parser, PGG takes as input a translation module to generate a parser-generator. The translation module plays a role to translate an abstracted parser into a concrete parser written in your language. Implementing the translation module may seem difficult, but don't worry. PGG provides you with most implementation of it and you only have to implement simple functions and customize some variables with provided information. See Implementing Translation module .

The input-specification format of PGG-generated parser-generator(PGG parser-generator) is based on that of the existing parser-generator Ocamlyacc. If you are already familiar to Ocamlyacc, you will easily adapt yourself to the input specification format of PGG parser-generator. Between Ocamlyacc and PGG parser-generator input-specifications, only three differences exist; 1) header and trailer sections are divided into two subsections, 2) types of non-terminal symbols should be explicitly declared, 3) a new keyword '@' is introduced as a method to access information about token position. See Input-specification of PGG parser-generator.

According to our experiments, performances of parsers generated from PGG parser-generators are generally poor than parsers generated from existing parsers. When we measured elapsed time to parse all implementation files(*.ml, 597files, 85384lines) of Ocaml sources distribution(version 3.10.0) by using two Ocaml parsers generated from PGG parser-generator and Ocamlyacc, PGG parser is 4~5 seconds slower than Ocamlyacc parser. However, think about effort to imlpement a parser-generator. You can choose: struggle against complex algorithms to implement your parser-generator for a week, or use PGG to implement your own parser-generator just in several hours.

Requirements

• Your target language should contain following syntactic components which are classified to four groups:
  
  * Declaration : Type declaration, Value declaration, Function declaration
  - Type declaration includes type aliasing.
  - Function declaration includes recursive function declaration.
  
  * Type : Type identifier, Type tuple
  - Type tuple expresses multiple types.
  
  * Pattern : Pattern identifier, Pattern tuple, Pattern constructor, Pattern constant
  - Pattern constructor may have a parameter.
  - Pattern constant expresses integer type only.
  
  * Expression : Identifier, Tuple, Constructor, Constant, Function application, Let-binding, Pattern-matching
  - Let-binding consists of value binding and function binding.

• Your target language should have a module system. A method to open a module path (open in Ocaml) is also required.

• You need a lexical analyzer to produce tokens.

How to use PGG

• PGG requires GNU gcc and make in the Unix environment. We have tested it only on Debian Linux 2.6.21-6, but any programming environment with GNU gcc and make should be fine.

• Download PGG.tar.gz or PGG.zip, and uncompress it in your installation directory.

• Implement a translation module : open transaltor.c and modify it for your own programming language (initially, it is for Ocaml) [details].

• Open 'Makefile' and change the variable 'PROGRAM' to your own parser-generator name(eg. PGG_Ocaml -> PGG_Mylang)

• Run 'make'.

• Write an input-specification (eg.cal.y) [details].

• Run '($PROGRAM) input-spec' (eg. 'PGG_Mylang cal.y') to generate a parser which consists of two files; token-output file (sample) and parser-output file (sample).
  Run '($PROGRAM) -v input-spec' (eg. 'PGG_Mylang -v cal.y') to generate a human-readable description of the generated parser.

• Compile generated codes in the following order: 1) token-output file, 2) lexical analyzer, 3) parser-output file, 4) main programs.

Implementing Translation module

(1) Customizing variables

• First, decide suffixes of output files:

  char *output_suffix = ".ml";
  char *token_suffix = "_token.ml";
  

  These two variables decide suffixes of two output files which are generated by PGG-generated parser; token-output file that contains the definition of token type and parser-output file that contains the main parser program. For example, if you defines them as above and PGG-generated parser takes 'a.y' as input-specification, it yields a.ml and a_token.ml as the parser-output file and the token-output file respectively.

• Define names of type constructors that are internally used in PGG:

  char *token_tycon = "token";
  char *state_tycon = "state";
  char *location_tycon = "location";
  char *stack_elem_tycon = "stack_elem";
  char *stack_tycon = "stack";
  char *next_action_tycon = "next_act";
  char *result_tycon = "result";
  

  Since the lexical convention of type constructor names is different according to the target language, you have to define each type constructor name to be appropriate to the lexical convention of your language. For example, for Haskell, you should replace the first character of each name with a upper-case character due to its lexical convention. (eg. "Token", "State" ..).

• Define the stack type and location type:

  char *define_stack_type = "stack_elem list";
  char *define_location_type = "int";
  

  You may simply define the stack type and location type by using list and int as above. Otherwise, you may modify these. For example, if you want more detailed location including a start location and an end location, you may define the location type as int * int to represents start and end locations.

• Define the dummy location and the empty stack:

  char *define_dummy_location = "-1";
  char *define_stack_empty = "[]";
  

  define_dummy_location represents the dummy location which is necessary for PGG. You should assign this variable a meaningless value whose type is previously defined location type. If the location type is int * int, you should assign a value such as (-1,-1). define stack empty represents the empty stack implementation.

• Finally, Implement stack functions; push and pop whose types are as follows:

  push : stack elem -> stack -> stack
  pop : stack -> stack elem * stack
  

  push has two arguments whose names are; elem and st. pop has one arguments whose name is st. You may simply implement these two functions by using these arguments as follows:

  char *define_stack_push = "elem::st";
  char *define_stack_pop = "
  match st with
  | head::st' -> (head,st')";
  

  In the pop function, since stack is never empty before parsing is completed, you need not concern such case.

• You should implement 18 translation functions:

  * Declaration

  void prt_decl_TYPE(FILE * fp ,struct d_type *d);
  void prt_decl_TYPE_ALIAS(FILE * fp ,struct d_type_alias *d);
  void prt_decl_VAL(FILE *fp, struct d_val *d);
  void prt_decl_FUNC(FILE *fp, struct d_func *d);
  

  * Type

  void prt_type_IDENT (FILE *fp, struct t_ident *t);
  void prt_type_TUPLE (FILE *fp, struct t_tuple *t);
  

  * Pattern

  void prt_pattern_IDENT (FILE *fp, struct p_ident *p);
  void prt_pattern_TUPLE (FILE *fp, struct p_tuple *p);
  void prt_pattern_CONSTRUCTOR (FILE *fp, struct p_constructor *p);
  void prt_pattern_CONSTANT (FILE *fp, struct p_constant *p);
  

  * Expression

  void prt_expression_IDENT (FILE *fp, struct e_ident *e);
  void prt_expression_TUPLE (FILE *fp, struct e_tuple *e);
  void prt_expression_CONSTRUCTOR (FILE *fp, struct e_constructor *e);
  void prt_expression_CONSTANT (FILE *fp, struct e_constant *e);
  void prt_expression_APPLY (FILE *fp, struct e_apply *e);
  void prt_expression_LET_VAL (FILE *fp, struct e_let_val *e);
  void prt_expression_LET_FUNC (FILE *fp, struct e_let_func *e);
  void prt_expression_MATCH (FILE *fp, struct e_match *e);
  

• PGG provides all information to implement above functions. You can implement your own translation function by using given information and modifying existing function for Ocaml. As an example, we show how to implement the translation function for pattern-matching whose function header is as follow:

   void prt_decl_TYPE(FILE * fp ,struct d_type *d)

  fp is the file pointer of outputs and d includes all information to describe type declaration syntax. PGG comments information about this function like this:

  /* prt_decl_TYPE 
   * 
   * 1) references
   * struct d_type { int num_ctlist; string tcon_id; CON_TYPE* ctlist; }; 
   * struct con_type { string con_id; TYPEXPR t;};
   *
   * 2) output 
   *  type <tcon_id> = 
   *  | <ctlist[0]->con_id> { of <ctlist[0] -> t> }
   *  | <ctlist[1]->con_id> { of <ctlist[1] -> t> }
   *  | .. 
   */
  

  '1) references' shows member-variables of given data structures and '2) output' shows output code written in Ocaml syntax. PGG also provides implementation for Ocaml as follow:

  void prt_decl_TYPE(FILE* fp, struct d_type *d)
  {
      int i;
      fprintf(fp,"type %s = ",d->tcon_id);
      for(i=0; i<d->num_ctlist; i++)
      {
          fprintf(fp,"\n   | ");
          if (d->ctlist[i]->t)
          {
              fprintf(fp,"%s of ",d->ctlist[i]->con_id);
              prt_type(fp,d->ctlist[i]->t);
          }
          else fprintf(fp,"%s",d->ctlist[i]->con_id);
      }
  }
  

  From this, you can find how to access information to describe type declaration syntax.

• Suppose your target language is SML. type declaration syntax of SML is as follow:

  datatype typename =
    constructor {of typexpr}
  | constructor {of typexpr}
  | ...
  

  You can easily modify void prt_decl_TYPE() to express above syntax like this:

  void prt_decl_TYPE(FILE* fp, struct d_type *d)
  {
      int i;
      fprintf(fp,"datatype %s = ",d->tcon_id);
      for(i=0; inum_ctlist; i++)
      {
          fprintf(fp,"\n   ");
          if (i!=0)
              fprintf(fp,"| ");
          if (d->ctlist[i]->t)
          {
              fprintf(fp,"%s of ",d->ctlist[i]->con_id);
              prt_type(fp,d->ctlist[i]->t);
          }
          else fprintf(fp,"%s",d->ctlist[i]->con_id);
      }
  } 
  

Input-specification of PGG parser-generator

• We compare two input-specifications to show differences of them which are highlighted:

  Ocamlyacc input-specification

  PGG input-specification

  /* header */ %{ %} /* beginning of declarations section */ %token DOT %token <string> CHAR %token EOF %start start_list %type <string list> start_list %% /* beginning of rules section */ start_list : list EOF {$1} ; list : list DOT element { $3 :: $1 } | element {[$1]} ; element : CHAR { $1 } ; %% /* trailer */

  /* token header*/ %[ %] /* parser header */ %{ open Test_token let lexfun lb = let token = Lexer.token lb in (token,lb.Lexing.lex_curr_pos,lb) %} /* beginning of declarations section */ %token DOT %token <string> CHAR %token EOF %start start_list %type <string list> start_list %type <string list> list %type <string> element %% /* beginning of rules section */ start_list : list EOF {$1} ; list : list DOT element { $3 :: $1 } | element {[$1]} ; element : CHAR { print string "CHAR location :"; print_int @1; $1 } ; %% /* token trailer */ %% /* parser trailer */

• The header section is divided into two subsections; token header and parser header because PGG parser-generator generates two output files; the token-output file which contains the token module and the parser-output file which contain the main module of parser. As in the case of Ocamlyacc, the code written in each header is emitted verbatim into the top of each output file respectively.

• In parser header, you should open your token module (in this case, Test_token) which is contained in the token-output file. Additionally, you should define lexfun whose type is as follow:

  lexfun : lexbuf -> token * location * lexbuf
  

  lexbuf is the type of input stream buffer. lexfun takes as input lexbuf and outputs a token(token), position of the token(location) and an updated input stream buffer(lexbuf). Lexer.token is an external lexical analyzer to produce tokens.

• In the Ocamlyacc input-specification, tokens (terminal-symbols) and the semantic type of start symbol (start list) are declared. However, PGG input-specification needs to know additional information about non-terminals such as list and element. You should additionally declare the semantic value type of each non-terminal symbols. If no type declaration about non-terminal list is specified, PGG parser-generator outputs an error message:

  No type has been declared for the non-terminal symbol "list"
  

• A keyword '@' is introduced as a method to access the location of specified symbol. The way to use this is similar to '$' which is a method to access the semantic value of each symbol in the given rule. In order to access semantic values of the first and second symbol, for example, we use $1 and $2. In the same way, we use @1 and @2 to access the location of each symbol.

• As the header section, the trailer section is also divided into two subsections; token trailer and parser trailer. Each section is separated by %%. The code written in each trailer emitted verbatim into the bottom of generated output files respectively.

Invoking PGG parser

• To cause parsing to occur, you call the parsing function. whose name is the same as that of start symbol. For example, in the case of the above PGG input-specification, the name of parsing function name is start_list.

• The type of parsing function is lexbuf -> result . lexbuf is the type of input stream and result is declared in the parser-output file as follow:

  type result_start_list =
    OK_start_list of string_list
  | Fail_start_list of location
  

  PGG parser informs you of the result of parsing by providing OK_ with parsing result or Fail with the location of an error.

• Here is an example of invoking a parser written in myParser.ml:

   let program inputfile =
   let ic = open_in_bin inputfile in
   let lexbuf = Lexing.from_channel ic in
   let result = MyParser.start_list lexbuf in
    match result with
    | MyParser.OK_start_list r -> r
    | MyParser.Fail_start_list loc -> print_error loc
  

Examples

Translation module for SML [Download]

---

Email us at .

Programming Language Laboratory

Department of Computer Science and Engineering

Pohang University of Science and Technology

Republic of Korea