Tcl Library Source Code

Documentation
Login


[ Main Table Of Contents | Table Of Contents | Keyword Index | Categories | Modules | Applications ]

NAME

pt::peg::to::param - PEG Conversion. Write PARAM format

Table Of Contents

SYNOPSIS

package require Tcl 8.5 9
package require pt::peg::to::param ?1.1?
package require pt::peg
package require pt::pe

pt::peg::to::param reset
pt::peg::to::param configure
pt::peg::to::param configure option
pt::peg::to::param configure option value...
pt::peg::to::param convert serial

DESCRIPTION

Are you lost ? Do you have trouble understanding this document ? In that case please read the overview provided by the Introduction to Parser Tools. This document is the entrypoint to the whole system the current package is a part of.

This package implements the converter from parsing expression grammars to PARAM markup.

It resides in the Export section of the Core Layer of Parser Tools, and can be used either directly with the other packages of this layer, or indirectly through the export manager provided by pt::peg::export. The latter is intented for use in untrusted environments and done through the corresponding export plugin pt::peg::export::param sitting between converter and export manager.

API

The API provided by this package satisfies the specification of the Converter API found in the Parser Tools Export API specification.

Options

The converter to PARAM markup recognizes the following configuration variables and changes its behaviour as they specify.

PARAM code representation of parsing expression grammars

The PARAM code representation of parsing expression grammars is assembler-like text using the instructions of the virtual machine documented in the PackRat Machine Specification, plus a few more for control flow (jump ok, jump fail, call symbol, return).

It is not really useful, except possibly as a tool demonstrating how a grammar is compiled in general, without getting distracted by the incidentials of a framework, i.e. like the supporting C and Tcl code generated by the other PARAM-derived formats.

It has no direct formal specification beyond what was said above.

Example

Assuming the following PEG for simple mathematical expressions

PEG calculator (Expression)
    Digit      <- '0'/'1'/'2'/'3'/'4'/'5'/'6'/'7'/'8'/'9'       ;
    Sign       <- '-' / '+'                                     ;
    Number     <- Sign? Digit+                                  ;
    Expression <- Term (AddOp Term)*                            ;
    MulOp      <- '*' / '/'                                     ;
    Term       <- Factor (MulOp Factor)*                        ;
    AddOp      <- '+'/'-'                                       ;
    Factor     <- '(' Expression ')' / Number                   ;
END;

one possible PARAM serialization for it is

# -*- text -*-
# Parsing Expression Grammar 'TEMPLATE'.
# Generated for unknown, from file 'TEST'

#
# Grammar Start Expression
#

<<MAIN>>:
         call              sym_Expression
         halt

#
# value Symbol 'AddOp'
#

sym_AddOp:
# /
#     '-'
#     '+'

         symbol_restore    AddOp
  found! jump              found_7
         loc_push

         call              choice_5

   fail! value_clear
     ok! value_leaf        AddOp
         symbol_save       AddOp
         error_nonterminal AddOp
         loc_pop_discard

found_7:
     ok! ast_value_push
         return

choice_5:
# /
#     '-'
#     '+'

         error_clear

         loc_push
         error_push

         input_next        "t -"
     ok! test_char         "-"

         error_pop_merge
     ok! jump              oknoast_4

         loc_pop_rewind
         loc_push
         error_push

         input_next        "t +"
     ok! test_char         "+"

         error_pop_merge
     ok! jump              oknoast_4

         loc_pop_rewind
         status_fail
         return

oknoast_4:
         loc_pop_discard
         return
#
# value Symbol 'Digit'
#

sym_Digit:
# /
#     '0'
#     '1'
#     '2'
#     '3'
#     '4'
#     '5'
#     '6'
#     '7'
#     '8'
#     '9'

         symbol_restore    Digit
  found! jump              found_22
         loc_push

         call              choice_20

   fail! value_clear
     ok! value_leaf        Digit
         symbol_save       Digit
         error_nonterminal Digit
         loc_pop_discard

found_22:
     ok! ast_value_push
         return

choice_20:
# /
#     '0'
#     '1'
#     '2'
#     '3'
#     '4'
#     '5'
#     '6'
#     '7'
#     '8'
#     '9'

         error_clear

         loc_push
         error_push

         input_next        "t 0"
     ok! test_char         "0"

         error_pop_merge
     ok! jump              oknoast_19

         loc_pop_rewind
         loc_push
         error_push

         input_next        "t 1"
     ok! test_char         "1"

         error_pop_merge
     ok! jump              oknoast_19

         loc_pop_rewind
         loc_push
         error_push

         input_next        "t 2"
     ok! test_char         "2"

         error_pop_merge
     ok! jump              oknoast_19

         loc_pop_rewind
         loc_push
         error_push

         input_next        "t 3"
     ok! test_char         "3"

         error_pop_merge
     ok! jump              oknoast_19

         loc_pop_rewind
         loc_push
         error_push

         input_next        "t 4"
     ok! test_char         "4"

         error_pop_merge
     ok! jump              oknoast_19

         loc_pop_rewind
         loc_push
         error_push

         input_next        "t 5"
     ok! test_char         "5"

         error_pop_merge
     ok! jump              oknoast_19

         loc_pop_rewind
         loc_push
         error_push

         input_next        "t 6"
     ok! test_char         "6"

         error_pop_merge
     ok! jump              oknoast_19

         loc_pop_rewind
         loc_push
         error_push

         input_next        "t 7"
     ok! test_char         "7"

         error_pop_merge
     ok! jump              oknoast_19

         loc_pop_rewind
         loc_push
         error_push

         input_next        "t 8"
     ok! test_char         "8"

         error_pop_merge
     ok! jump              oknoast_19

         loc_pop_rewind
         loc_push
         error_push

         input_next        "t 9"
     ok! test_char         "9"

         error_pop_merge
     ok! jump              oknoast_19

         loc_pop_rewind
         status_fail
         return

oknoast_19:
         loc_pop_discard
         return
#
# value Symbol 'Expression'
#

sym_Expression:
# /
#     x
#         '\('
#         (Expression)
#         '\)'
#     x
#         (Factor)
#         *
#             x
#                 (MulOp)
#                 (Factor)

         symbol_restore    Expression
  found! jump              found_46
         loc_push
         ast_push

         call              choice_44

   fail! value_clear
     ok! value_reduce      Expression
         symbol_save       Expression
         error_nonterminal Expression
         ast_pop_rewind
         loc_pop_discard

found_46:
     ok! ast_value_push
         return

choice_44:
# /
#     x
#         '\('
#         (Expression)
#         '\)'
#     x
#         (Factor)
#         *
#             x
#                 (MulOp)
#                 (Factor)

         error_clear

         ast_push
         loc_push
         error_push

         call              sequence_27

         error_pop_merge
     ok! jump              ok_43

         ast_pop_rewind
         loc_pop_rewind
         ast_push
         loc_push
         error_push

         call              sequence_40

         error_pop_merge
     ok! jump              ok_43

         ast_pop_rewind
         loc_pop_rewind
         status_fail
         return

ok_43:
         ast_pop_discard
         loc_pop_discard
         return

sequence_27:
# x
#     '\('
#     (Expression)
#     '\)'

         loc_push
         error_clear

         error_push

         input_next        "t ("
     ok! test_char         "("

         error_pop_merge
   fail! jump              failednoast_29
         ast_push
         error_push

         call              sym_Expression

         error_pop_merge
   fail! jump              failed_28
         error_push

         input_next        "t )"
     ok! test_char         ")"

         error_pop_merge
   fail! jump              failed_28

         ast_pop_discard
         loc_pop_discard
         return

failed_28:
         ast_pop_rewind

failednoast_29:
         loc_pop_rewind
         return

sequence_40:
# x
#     (Factor)
#     *
#         x
#             (MulOp)
#             (Factor)

         ast_push
         loc_push
         error_clear

         error_push

         call              sym_Factor

         error_pop_merge
   fail! jump              failed_41
         error_push

         call              kleene_37

         error_pop_merge
   fail! jump              failed_41

         ast_pop_discard
         loc_pop_discard
         return

failed_41:
         ast_pop_rewind
         loc_pop_rewind
         return

kleene_37:
# *
#     x
#         (MulOp)
#         (Factor)

         loc_push
         error_push

         call              sequence_34

         error_pop_merge
   fail! jump              failed_38
         loc_pop_discard
         jump              kleene_37

failed_38:
         loc_pop_rewind
         status_ok
         return

sequence_34:
# x
#     (MulOp)
#     (Factor)

         ast_push
         loc_push
         error_clear

         error_push

         call              sym_MulOp

         error_pop_merge
   fail! jump              failed_35
         error_push

         call              sym_Factor

         error_pop_merge
   fail! jump              failed_35

         ast_pop_discard
         loc_pop_discard
         return

failed_35:
         ast_pop_rewind
         loc_pop_rewind
         return
#
# value Symbol 'Factor'
#

sym_Factor:
# x
#     (Term)
#     *
#         x
#             (AddOp)
#             (Term)

         symbol_restore    Factor
  found! jump              found_60
         loc_push
         ast_push

         call              sequence_57

   fail! value_clear
     ok! value_reduce      Factor
         symbol_save       Factor
         error_nonterminal Factor
         ast_pop_rewind
         loc_pop_discard

found_60:
     ok! ast_value_push
         return

sequence_57:
# x
#     (Term)
#     *
#         x
#             (AddOp)
#             (Term)

         ast_push
         loc_push
         error_clear

         error_push

         call              sym_Term

         error_pop_merge
   fail! jump              failed_58
         error_push

         call              kleene_54

         error_pop_merge
   fail! jump              failed_58

         ast_pop_discard
         loc_pop_discard
         return

failed_58:
         ast_pop_rewind
         loc_pop_rewind
         return

kleene_54:
# *
#     x
#         (AddOp)
#         (Term)

         loc_push
         error_push

         call              sequence_51

         error_pop_merge
   fail! jump              failed_55
         loc_pop_discard
         jump              kleene_54

failed_55:
         loc_pop_rewind
         status_ok
         return

sequence_51:
# x
#     (AddOp)
#     (Term)

         ast_push
         loc_push
         error_clear

         error_push

         call              sym_AddOp

         error_pop_merge
   fail! jump              failed_52
         error_push

         call              sym_Term

         error_pop_merge
   fail! jump              failed_52

         ast_pop_discard
         loc_pop_discard
         return

failed_52:
         ast_pop_rewind
         loc_pop_rewind
         return
#
# value Symbol 'MulOp'
#

sym_MulOp:
# /
#     '*'
#     '/'

         symbol_restore    MulOp
  found! jump              found_67
         loc_push

         call              choice_65

   fail! value_clear
     ok! value_leaf        MulOp
         symbol_save       MulOp
         error_nonterminal MulOp
         loc_pop_discard

found_67:
     ok! ast_value_push
         return

choice_65:
# /
#     '*'
#     '/'

         error_clear

         loc_push
         error_push

         input_next        "t *"
     ok! test_char         "*"

         error_pop_merge
     ok! jump              oknoast_64

         loc_pop_rewind
         loc_push
         error_push

         input_next        "t /"
     ok! test_char         "/"

         error_pop_merge
     ok! jump              oknoast_64

         loc_pop_rewind
         status_fail
         return

oknoast_64:
         loc_pop_discard
         return
#
# value Symbol 'Number'
#

sym_Number:
# x
#     ?
#         (Sign)
#     +
#         (Digit)

         symbol_restore    Number
  found! jump              found_80
         loc_push
         ast_push

         call              sequence_77

   fail! value_clear
     ok! value_reduce      Number
         symbol_save       Number
         error_nonterminal Number
         ast_pop_rewind
         loc_pop_discard

found_80:
     ok! ast_value_push
         return

sequence_77:
# x
#     ?
#         (Sign)
#     +
#         (Digit)

         ast_push
         loc_push
         error_clear

         error_push

         call              optional_70

         error_pop_merge
   fail! jump              failed_78
         error_push

         call              poskleene_73

         error_pop_merge
   fail! jump              failed_78

         ast_pop_discard
         loc_pop_discard
         return

failed_78:
         ast_pop_rewind
         loc_pop_rewind
         return

optional_70:
# ?
#     (Sign)

         loc_push
         error_push

         call              sym_Sign

         error_pop_merge
   fail! loc_pop_rewind
     ok! loc_pop_discard
         status_ok
         return

poskleene_73:
# +
#     (Digit)

         loc_push

         call              sym_Digit

   fail! jump              failed_74

loop_75:
         loc_pop_discard
         loc_push
         error_push

         call              sym_Digit

         error_pop_merge
     ok! jump              loop_75
         status_ok

failed_74:
         loc_pop_rewind
         return
#
# value Symbol 'Sign'
#

sym_Sign:
# /
#     '-'
#     '+'

         symbol_restore    Sign
  found! jump              found_86
         loc_push

         call              choice_5

   fail! value_clear
     ok! value_leaf        Sign
         symbol_save       Sign
         error_nonterminal Sign
         loc_pop_discard

found_86:
     ok! ast_value_push
         return
#
# value Symbol 'Term'
#

sym_Term:
# (Number)

         symbol_restore    Term
  found! jump              found_89
         loc_push
         ast_push

         call              sym_Number

   fail! value_clear
     ok! value_reduce      Term
         symbol_save       Term
         error_nonterminal Term
         ast_pop_rewind
         loc_pop_discard

found_89:
     ok! ast_value_push
         return

#
#

PEG serialization format

Here we specify the format used by the Parser Tools to serialize Parsing Expression Grammars as immutable values for transport, comparison, etc.

We distinguish between regular and canonical serializations. While a PEG may have more than one regular serialization only exactly one of them will be canonical.

Example

Assuming the following PEG for simple mathematical expressions

PEG calculator (Expression)
    Digit      <- '0'/'1'/'2'/'3'/'4'/'5'/'6'/'7'/'8'/'9'       ;
    Sign       <- '-' / '+'                                     ;
    Number     <- Sign? Digit+                                  ;
    Expression <- Term (AddOp Term)*                            ;
    MulOp      <- '*' / '/'                                     ;
    Term       <- Factor (MulOp Factor)*                        ;
    AddOp      <- '+'/'-'                                       ;
    Factor     <- '(' Expression ')' / Number                   ;
END;

then its canonical serialization (except for whitespace) is

pt::grammar::peg {
    rules {
        AddOp      {is {/ {t -} {t +}}                                                                mode value}
        Digit      {is {/ {t 0} {t 1} {t 2} {t 3} {t 4} {t 5} {t 6} {t 7} {t 8} {t 9}}                mode value}
        Expression {is {x {n Term} {* {x {n AddOp} {n Term}}}}                                        mode value}
        Factor     {is {/ {x {t (} {n Expression} {t )}} {n Number}}                                  mode value}
        MulOp      {is {/ {t *} {t /}}                                                                mode value}
        Number     {is {x {? {n Sign}} {+ {n Digit}}}                                                 mode value}
        Sign       {is {/ {t -} {t +}}                                                                mode value}
        Term       {is {x {n Factor} {* {x {n MulOp} {n Factor}}}}                                    mode value}
    }
    start {n Expression}
}

PE serialization format

Here we specify the format used by the Parser Tools to serialize Parsing Expressions as immutable values for transport, comparison, etc.

We distinguish between regular and canonical serializations. While a parsing expression may have more than one regular serialization only exactly one of them will be canonical.

Example

Assuming the parsing expression shown on the right-hand side of the rule

Expression <- Term (AddOp Term)*

then its canonical serialization (except for whitespace) is

{x {n Term} {* {x {n AddOp} {n Term}}}}

Bugs, Ideas, Feedback

This document, and the package it describes, will undoubtedly contain bugs and other problems. Please report such in the category pt of the Tcllib Trackers. Please also report any ideas for enhancements you may have for either package and/or documentation.

When proposing code changes, please provide unified diffs, i.e the output of diff -u.

Note further that attachments are strongly preferred over inlined patches. Attachments can be made by going to the Edit form of the ticket immediately after its creation, and then using the left-most button in the secondary navigation bar.

KEYWORDS

EBNF, LL(k), PARAM, PEG, TDPL, context-free languages, conversion, expression, format conversion, grammar, matching, parser, parsing expression, parsing expression grammar, push down automaton, recursive descent, serialization, state, top-down parsing languages, transducer

CATEGORY

Parsing and Grammars

COPYRIGHT

Copyright © 2009 Andreas Kupries