# Parser beginner needs help

**URL:** <https://discuss.ocaml.org/t/parser-beginner-needs-help/4472>\
**Category:** Learning\
**Tags:** parser\
**Created:** [October 1, 2019, 7:25pm UTC](https://discuss.ocaml.org/t/parser-beginner-needs-help/4472 "2019-10-01T19:25:53Z")\
**Posts on this page:** 4\
**Page:** 1

<div class="post-metadata">

**Author:** ![phstrauss](https://avatars.discourse-cdn.com/v4/letter/p/4da419/32.png) [@phstrauss](https://discuss.ocaml.org/u/phstrauss)\
**Post date:** [October 1, 2019, 7:25pm UTC](https://discuss.ocaml.org/t/parser-beginner-needs-help/4472/1 "2019-10-01T19:25:53Z")

</div>

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](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! 🙂

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

Many thanks for any help

---

<div class="post-metadata">

**Author:** ![SkySkimmer](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/skyskimmer/32/1672_2.png) [@SkySkimmer](https://discuss.ocaml.org/u/SkySkimmer)\
**Post date:** [October 1, 2019, 8:41pm UTC](https://discuss.ocaml.org/t/parser-beginner-needs-help/4472/2 "2019-10-01T20:41:04Z")

</div>

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

```auto
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

```auto
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

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

```

and remove the `List.rev` uses.

---

<div class="post-metadata">

**Author:** ![cloudyhug](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/cloudyhug/32/2399_2.png) [@cloudyhug](https://discuss.ocaml.org/u/cloudyhug)\
**Post date:** [October 1, 2019, 9:38pm UTC](https://discuss.ocaml.org/t/parser-beginner-needs-help/4472/3 "2019-10-01T21:38:34Z")

</div>

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…

```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](http://dev.realworldocaml.org/parsing-with-ocamllex-and-menhir.html) they explain right-recursive rules are inefficient.

---

<div class="post-metadata">

**Author:** ![phstrauss](https://avatars.discourse-cdn.com/v4/letter/p/4da419/32.png) [@phstrauss](https://discuss.ocaml.org/u/phstrauss)\
**Post date:** [October 5, 2019, 7:11am UTC](https://discuss.ocaml.org/t/parser-beginner-needs-help/4472/4 "2019-10-05T07:11:25Z")

</div>

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

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

cloudy hug is right about the rev list BTW.