# Implement context dependent language with ocamlyacc **URL:** \ **Category:** Learning\ **Tags:** compiler\ **Created:** [June 16, 2023, 6:01am UTC](https://discuss.ocaml.org/t/implement-context-dependent-language-with-ocamlyacc/12418 "2023-06-16T06:01:00Z")\ **Posts on this page:** 9\ **Page:** 1
**Author:** ![Tom\_H](https://avatars.discourse-cdn.com/v4/letter/t/5e9695/32.png) [@Tom\_H](https://discuss.ocaml.org/u/Tom_H)\ **Post date:** [June 16, 2023, 6:01am UTC](https://discuss.ocaml.org/t/implement-context-dependent-language-with-ocamlyacc/12418/1 "2023-06-16T06:01:00Z")
Hi there, I am implementing a context-dependent language, and this language supports custom typedef, pointer and multiplication. So there are two possible parser trees for the expression below ```auto foo * bar; ``` 1. variable `foo` multiplies variable `bar` 2. declare a pointer `bar` of type `foo` My grammar cannot handle this situation yet: ```auto simp : | t = dtype; ident = Ident; { Cst.New_var { t = t; name = ident } } | e = exp; { Cst.Sexp e } | other rules exp : | lhs = exp; Star; rhs = exp; | other rules ``` My plan is to add a mutable set in the header. This set will store custom type during parsing. If `foo` is a declared type, then it will parse it as a declare statement. Otherwise, it will treat it as a multiplication. However, I am not sure how to use this mutable set to determine which rule to apply ☹ I am not even sure if this approach is correct… Any ideas would be grateful! ---
**Author:** ![ancolie](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/ancolie/32/6189_2.png) [@ancolie](https://discuss.ocaml.org/u/ancolie)\ **Post date:** [June 16, 2023, 6:27am UTC](https://discuss.ocaml.org/t/implement-context-dependent-language-with-ocamlyacc/12418/2 "2023-06-16T06:27:07Z")
You could have a first `exp` type which would be something like `type exp = ... | Star of string * string`. Then, you would write an OCaml function `exp -> exp'` with `type exp' = ... | Mul of string * string | Ptr of string * string`. This would avoid having to do too complex things in the parser. Are you designing the language ? If yes, the better solution would probably be to change the syntax to avoid the problem. Is the multiplication only going to happen on the right-hand side of a assignment: `int x = y * z;` ? If so, I believe you can fix the problem directly in the parser without introducing a mutable set or whatever. ---
**Author:** ![Tom\_H](https://avatars.discourse-cdn.com/v4/letter/t/5e9695/32.png) [@Tom\_H](https://discuss.ocaml.org/u/Tom_H)\ **Post date:** [June 16, 2023, 7:01am UTC](https://discuss.ocaml.org/t/implement-context-dependent-language-with-ocamlyacc/12418/3 "2023-06-16T07:01:04Z")
Thank you for your reply! > Are you designing the language? In fact, I am self-studying a compiler course, and this is its [assignment](https://www.cs.cmu.edu/afs/cs/academic/class/15411-f20/www/hw/lab4.pdf). It is basically a simplified version of C. I copied the syntax below ![截屏2023-06-16 15.07.43](https://us1.discourse-cdn.com/flex020/uploads/ocaml/original/2X/c/ca62312fb5720e25bbab39b679e753d107046610.png) `type exp = ... | Star of string * string` seems to treat declaration as an expression, right? In fact, this approach is mentioned in the handout, but it states > One way to handle this is to perform an ambiguous parse: use one rule to parse both the > declaration form and the expression form. Then undo an incorrect decision during elaboration. This approach will almost certainly involve some other adjustment to various pieces of your grammar and lexer. Looking over grammars and parsers from past years, we cannot honestly recommend this technique—results seem to be largely contorted with low confidence in correctness. > Is the multiplication only going to happen on the right-hand side of a assignment: `int x = y * z;` ? Sadly, an expression can be a statement just for potential side-effect(like 0/0) in this language. So `y * z;` is just legal. ---
**Author:** ![silene](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/silene/32/2707_2.png) [@silene](https://discuss.ocaml.org/u/silene)\ **Post date:** [June 16, 2023, 7:12am UTC](https://discuss.ocaml.org/t/implement-context-dependent-language-with-ocamlyacc/12418/4 "2023-06-16T07:12:32Z")
> [@Tom\_H](#): > > I am not even sure if this approach is correct… I suggest to go with the solution described in your assignment: “the parser can update mutable state to record type identifiers as such. With this approach, the lexer can produce different tokens for type and non-type identifiers.” Making the lexer a bit smarter is much easier than making the parser context-dependent. ---
**Author:** ![Tom\_H](https://avatars.discourse-cdn.com/v4/letter/t/5e9695/32.png) [@Tom\_H](https://discuss.ocaml.org/u/Tom_H)\ **Post date:** [June 16, 2023, 7:23am UTC](https://discuss.ocaml.org/t/implement-context-dependent-language-with-ocamlyacc/12418/5 "2023-06-16T07:23:51Z")
Thank you for your suggestion! Modifying the lexer is indeed simpler. I am working on it and see if it goes well! ---
**Author:** ![Tom\_H](https://avatars.discourse-cdn.com/v4/letter/t/5e9695/32.png) [@Tom\_H](https://discuss.ocaml.org/u/Tom_H)\ **Post date:** [June 22, 2023, 5:43am UTC](https://discuss.ocaml.org/t/implement-context-dependent-language-with-ocamlyacc/12418/6 "2023-06-22T05:43:29Z")
I am sorry the title is misleading, it should be **Implement context dependent language with menhir**. I didn’t distinguish ocamlyacc and menhir before… I read the [menhir document](http://gallium.inria.fr/~fpottier/menhir/manual.pdf) and a related [post](https://discuss.ocaml.org/t/how-to-parse-a-token-with-a-list-argument-in-menhir/10567/3) that makes lexer a bit smarter. Now i got some clues but still need some helps. I am planning to return different tokens, say variable token and type token, according the same rule. snippet of .mll file looks like ```auto let ident = ['A'-'Z' 'a'-'z' '_']['A'-'Z' 'a'-'z' '0'-'9' '_']* rule initial type_set = parse | ident as name {if ident in type_set then TIdent name else VIdent name} ``` This `type_set` stores all type variables declared till now. So once a identifier is recognized, lexer can check if this identifier is a type variable or not. If it is a type variable, then return type ident token for parser, otherwise variable ident token. However, the key point now is how can I pass this `type_set` to lexer. I know ocamllex [allows to pass argument at entrypoint](https://www.iro.umontreal.ca/~monnier/3065/ocamllex-tutorial.pdf). However, these arguments seems to be internal. Can I pass these argument from parser(menhir)? ---
**Author:** ![silene](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/silene/32/2707_2.png) [@silene](https://discuss.ocaml.org/u/silene)\ **Post date:** [June 22, 2023, 6:27am UTC](https://discuss.ocaml.org/t/implement-context-dependent-language-with-ocamlyacc/12418/7 "2023-06-22T06:27:38Z")
The simplest solution is to have a global variable shared by both the lexer and the parser. This variable would contain a `Hashtbl` or a reference to a `Set`. The parser would update it and the lexer would read it. > [@Tom\_H](#): > > I know ocamllex [allows to pass argument at entrypoint](https://www.iro.umontreal.ca/~monnier/3065/ocamllex-tutorial.pdf). However, these arguments seems to be internal. Can I pass these argument from parser(menhir)? I am not sure what you mean by internal. Any extra argument in an ocamllex rule is part of the signature of the generated function. In particular, when you pass the lexbuf argument to the main lexer function during the initialization of the parser, you also pass all the extra arguments. If you do not want the above `Hashtbl` to be a global variable (e.g., because you want your lexer/parser to be reentrant), then you can create a local one during parser initialization and pass it to the lexer entrypoint. ---
**Author:** ![Tom\_H](https://avatars.discourse-cdn.com/v4/letter/t/5e9695/32.png) [@Tom\_H](https://discuss.ocaml.org/u/Tom_H)\ **Post date:** [June 22, 2023, 6:54am UTC](https://discuss.ocaml.org/t/implement-context-dependent-language-with-ocamlyacc/12418/8 "2023-06-22T06:54:32Z")
Thank you for elaboration! > [@silene](#): > > I am not sure what you mean by internal. Any extra argument in an ocamllex rule is part of the signature of the generated function. I found the [menhir manual](http://gallium.inria.fr/~fpottier/menhir/manual.pdf) page 30 indicate the signature for main parser function is ```auto val main: (Lexing.lexbuf -> token) -> Lexing.lexbuf -> thing ``` It seems that it only accepts lexer with signature `Lexing.lexbuf -> token`. So I said the lexer exposed to parser cannot have extra arguments. > [@silene](#): > > The simplest solution is to have a global variable shared by both the lexer and the parser I think a global variable shared between lexer and parser is great. I rarely use global variable across files, and it makes sense! > [@silene](#): > > you can create a local one during parser initialization and pass it to the lexer entrypoint. I am also quite interested in how to use local variable during parser initializations and pass it to the lexer entrypoint. In fact, even though it is successfully passed to lexer entrypoint, how can I update this variable in parser semantic actions(when parser detect a typedef variable)? ---
**Author:** ![silene](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/silene/32/2707_2.png) [@silene](https://discuss.ocaml.org/u/silene)\ **Post date:** [June 22, 2023, 7:26am UTC](https://discuss.ocaml.org/t/implement-context-dependent-language-with-ocamlyacc/12418/9 "2023-06-22T07:26:09Z")
> [@Tom\_H](#): > > It seems that it only accepts lexer with signature `Lexing.lexbuf -> token`. So I said the lexer exposed to parser cannot have extra arguments. Nobody forces you to pass the lexer function to the parser function in its original form. You can do arbitrary manipulations on it beforehand. In particular, you can pass all the missing arguments, so that both signatures match. > [@Tom\_H](#): > > A variable declared in mly/mll file header can be accessed within parser or lexer, but how to share it across lexer and parser? Eventually, both the lexer and the parser are transformed into plain OCaml files. If you define a global variable in a third OCaml file and both the lexer and the parser depends on this third file, then the variable is effectively shared. > [@Tom\_H](#): > > In fact, even though it is successfully passed to lexer entrypoint, how can I update this variable in parser semantic actions(when parser detect a typedef variable)? From the point of view of the parser, it is still a global variable, and it is modified as such. It is just that you do not need this global variable to be put into a separate file, since it is passed as an argument to the lexer function rather than being globally visible. But note that if you have declared your parser using the `%parameter` directive of Menhir, this global variable is actually a module-local one. So, you can have several separate instances of the parser, each with their own global variable. (I do not suggest to go that way, it is presumably not worth the effort.)