Parser beginner needs help

Learning
1

Hello OCamliens,

I’m trying to learn how to make a parser based on ocamllex and menhir.
The files on which I’m currently working on can be downloaded here :
http://www.strauss-engineering.ch/tmp/parser-mini.tgz
(guarantee without virus)

running « menhir config_parser_mini.mly » return an error, about my start symbol only being able to generate the {epsilon} language (the blank, empty string).

I’m sure a seasoned menhir or ocamlyacc user will spot whats wrong with my code in 30 seconds… Myself awaiting for your answer! :slight_smile:

PS: the file preamp.cfg is the example of the syntax I must become able to parse.

Many thanks for any help

2

For me it also says Warning: the token EOF is unused., if I put EOF at the end of both rules for config it compiles. ie

config:
| EOF                          { [] }
| setting_list EOF              { List.rev $1 }
;

Note however that setting_list can never be inhabited because it’s missing the empty case (or the only-1-setting case if you want nonempty lists). So maybe what you want is more like

config:
| setting_list EOF              { List.rev $1 }
;
setting_list:
| { [] }
| setting_list setting      { $2 :: $1 }
;

(you get a shift/reduce conflict because {} can parse to the empty list in 2 ways, remove the first rule for group to remove the conflict)

Finally I don’t know why you parse lists inverted, you can just do

setting_list:
| { [] }
| setting setting_list      { $1 :: $2 }
;

and remove the List.rev uses.

3

Hi. Not a regular menhir user, but I think the reverted list parsing allows complexity not to be quadratic. Indeed, in the setting_list setting solution, we already have a list, and we are recognising an additional token, so we put it at the front of the list. At the end, we need to reverse the final list, but it seems to be “linear”, whereas in the second option — setting setting_list — it looks like in order to process the setting token, we need to first make sure the end of the expression is a setting_list, so we need to process the N-1 elements before adding this one to the list.

As an analogy (below), map2 does not make the stack grow, whereas map1 fails with a huge list as input. I don’t know if it applies to parsers, but I think I might have read something talking about this in Real World OCaml…

let rec map1 f = function
  | [] -> []
  | x :: xs -> f x :: map1 f xs

let map2 f l =
  let rec build acc = function
    | [] -> List.rev acc
    | x :: xs -> build (f x :: acc) xs
  in build [] l

EDIT : at this page http://dev.realworldocaml.org/parsing-with-ocamllex-and-menhir.html they explain right-recursive rules are inefficient.

4

Thank you very much SkySkimmer for your help, I owe you a virtual beer and more :slight_smile:

.~~~~.
i====i
|cccc|_)
|cccc|
`-==-’

cloudy hug is right about the rev list BTW.

1 Like