PEG grammar for PL/0

[Geo-7]

I'm testing PEG and I want to replicate EBNF of PL/0
I've some problems :

1. The grammar only accept assignment with ; at the end and I could not add support for not having ; when the next line is end
2. I could not match one line if
3. Too many *ws
4. It's getting complicated & I still does not implement all of it.
   Any advise ?

(def pl-peg (peg/compile 
  ~{
    :main (* :block ".")
    :block (* (any (+ :const :var :procedure :statement :ws)))
    :ws (set " \t\r\f\n\0\v")
    :ws* (any :ws)
    :const (* "const" :const-assign (any (* "," :const-assign)) :end-st) 
    :const-assign (* :ident "=" (any :ws) :number)
    :var (* "var" :ident (any (* "," :ident)) :end-st)
    :procedure (* "procedure" :ident :end-st (any (+ :var :const)) :statement :end-st)
    :statement (+ :assign :call :question :not :loop :if (* :begin (any :statement) :end))
    :assign (* :ident ":=" :exp :end-st)
    :call (* "call" :ident :end-st)
    :question (* "?" :ident :end-st)
    :not (* "!" :ident :end-st)
    :if (* "if" :condition "then" :statement :end-st)
    :condition (* :exp (+ "#" "<=" ">=" "<" ">" "=") :exp)
    :loop (* "while" :condition "do" :statement)
    :end (* :ws* "end" :ws*)
    :begin (* :ws* "begin" :ws*)
    :exp1 (+ :ident :number)
    :exp (* :exp1 (any (* (+ "-" "+" "*" "/") :exp1)))
    :comment (* "{" (any (if-not "}" 1)) "}")
    :ident (* :ws* (some :a) :ws*)
    :number (* :ws* (some :d) :ws*)
    :end-st (* :ws* ";" :ws*)
    }))

EBNF example on wikipedia:

program = block "." ;

block = [ "const" ident "=" number {"," ident "=" number} ";"]
        [ "var" ident {"," ident} ";"]
        { "procedure" ident ";" block ";" } statement ;

statement = [ ident ":=" expression | "call" ident 
              | "?" ident | "!" expression 
              | "begin" statement {";" statement } "end" 
              | "if" condition "then" statement 
              | "while" condition "do" statement ];

condition = "odd" expression |
            expression ("="|"#"|"<"|"<="|">"|">=") expression ;

expression = [ "+"|"-"] term { ("+"|"-") term};

term = factor {("*"|"/") factor};

factor = ident | number | "(" expression ")";

[CosmicToast]

Welcome to parsing - it just is like this.
Parsing is ultimately an unsolved problem, meaning that there is no single best algorithm that will handle all of the desired cases.
Consequently, we have a language/grammar distinction: the language being the language that is being implemented, with the grammar being an implementation.

To this end, EBNF is a way to document the language.
You should see it more as a guideline rather than an actual implementation base.
Basically no matter what approach you take, you either will have to make changes or should make changes for performance reasons, even with a full parser-generator (which PEGs are not).

So, to answer your questions more accurately:

1. That's a problem with your grammar, it is entirely possible to do this, as PEGs are not line-oriented. The likely issue is that you do not allow the use of the "end" terminal inside of :end-st which you use quite often in place of :end. In short, it's an issue with your grammar.
2. You cannot match "if\n" because your grammar specifies the "if" terminal to be immediately followed by an ident or a number.
3. You will need a ws* wherever whitespace is allowed, yes. The way this is avoided in many parser generators is by putting an implicit one between the elements of every non-terminal, which can be quite undesirable.
4. Parsing is complicated.

I would recommend:

• Not including the whitespace inside your terminals (like :ident). You're going to want to capture those eventually, and surely var i; and var i; should refer to the same variable.
• Implement your language without worrying about the specifics of the EBNF. You can start by reproducing it faithfully (which you haven't really done here anyway, from what I can see), but don't be afraid to deviate. This applies to all parsing systems, and not just Janet's PEGs.

[Geo-7]

Thanks for your reply, for 1&2 I know that I've not implemented them, I tried but I failed. (handling one would cause problem for other one :end vs :end-st & multi line if vs one line ) I'm asking for hints.
3- sound reasonable, maybe I should remove ws* from ident, number, ...
4- Yesss.

[sogaiu]

Not really an answer, but sharing a sketch of an approach.

I tried gradually building up a series of smaller grammars (though I didn't finish), and made use of earlier ones via merge:

# program = block "." ;

# block = [ "const" ident "=" number {"," ident "=" number} ";"]
#         [ "var" ident {"," ident} ";"]
#         { "procedure" ident ";" block ";" } statement ;

# statement = [ ident ":=" expression | "call" ident 
#               | "?" ident | "!" expression 
#               | "begin" statement {";" statement } "end" 
#               | "if" condition "then" statement 
#               | "while" condition "do" statement ];

# condition = "odd" expression |
#             expression ("="|"#"|"<"|"<="|">"|">=") expression ;

# expression = [ "+"|"-"] term { ("+"|"-") term};

# term = factor {("*"|"/") factor};

# factor = ident | number | "(" expression ")";

(def number-grammar
  ~@{:main (sequence :number -1)
     :number (choice "0"
                     (sequence (range "19") :d*))})

(comment

  (peg/match number-grammar "0")
  # =>
  @[]

  (peg/match number-grammar "1")
  # =>
  @[]

  (peg/match number-grammar "1209")
  # =>
  @[]

  (peg/match number-grammar "a")
  # =>
  nil
  
  )

(def ident-grammar
  ~@{:main (sequence :ident -1)
     :ident (sequence :a (any :w))})

(comment

  (peg/match ident-grammar "a")
  # =>
  @[]

  (peg/match ident-grammar "bee")
  # =>
  @[]

  (peg/match ident-grammar "0")
  # =>
  nil
  
  )

(def expression-grammar
  (merge number-grammar
         ident-grammar
         ~@{:main (sequence :expression -1)
            :expression (sequence (opt (sequence (choice "+" "-") :s*))
                                  :term
                                  (any (sequence :s+ 
                                                 (choice "+" "-") :s*
                                                 :term)))
            :term (sequence :factor
                            (any (sequence :s+
                                           (choice "*" "/") :s+
                                           :factor)))
            :factor (choice :ident 
                            :number 
                            (sequence "(" :s* :expression :s* ")"))}))

(comment

  (peg/match expression-grammar "0")
  # =>
  @[]

  (peg/match expression-grammar "a")
  # =>
  @[]

  (peg/match expression-grammar "( x )")
  # =>
  @[]

  (peg/match expression-grammar "(y)")
  # =>
  @[]

  (peg/match expression-grammar "a * b / c")
  # =>
  @[]

  (peg/match expression-grammar "a * (b / c)")
  # =>
  @[]

  (peg/match expression-grammar "1 + 2 - 3")
  # =>
  @[]

  (peg/match expression-grammar "-789")
  # =>
  @[]

  )

(def condition-grammar
  (merge expression-grammar
         ~@{:main (sequence :condition -1)
            :condition 
            (choice (sequence "odd" :s+ :expression)
                    (sequence :expression :s+
                              (choice "=" "#" "<=" "<" ">=" ">") :s+
                              :expression))}))

(comment

  (peg/match condition-grammar "a = 0")
  # =>
  @[]

  (peg/match condition-grammar "x >= 0")
  # =>
  @[]

  (peg/match condition-grammar "i < -j")
  # =>
  @[]
  
  (peg/match condition-grammar "(1 + 2 - a) <= b")
  # =>
  @[]

  )

(def statement-grammar
  (merge condition-grammar
         ~@{:main (sequence :statement -1)
            :statement 
            (choice (sequence :ident :s+ ":=" :s+ :expression)
                    (sequence "call" :s+ :ident)
                    (sequence "?" :s* :ident)
                    (sequence "!" :s* :ident)
                    (sequence "begin" :s+ 
                              :statement
                              (any (sequence ";" :s+ :statement)) :s+
                              "end")
                    (sequence "if" :s+ 
                              :condition :s+
                              "then" :s+
                              :statement)
                    (sequence "while" :s+
                              :condition :s+
                              "do" :s+
                              :statement))}))

(comment

  (peg/match statement-grammar "call a")
  # =>
  @[]

  (peg/match statement-grammar "?b")
  # =>
  @[]

  (peg/match statement-grammar "!c")
  # =>
  @[]

  (peg/match statement-grammar
             ``
             begin
               call x
             end
             ``)
  # =>
  @[]

  (peg/match statement-grammar
             ``
             begin
               call x;
               begin
                 !b
               end
             end
             ``)
  # =>
  @[]

  (peg/match statement-grammar
             ``
             if a < b then
               x := y
             ``)
  # =>
  @[]

  (peg/match statement-grammar
             ``
             while x > 0 do
               x := x - 1
             ``)
  # =>
  @[]

  )