Git Product home page Git Product logo

Comments (10)

orangeduck avatar orangeduck commented on July 19, 2024

Hi ElArtista,

In all likeihood your grammar is left recursive, see:

https://github.com/orangeduck/mpc#the-parser-is-going-into-an-infinite-loop

I can't see right away with your specific grammar where it might be left recursive but perhaps reordering the options of type to put the base case (singletype) first will help.

  • Dan

from mpc.

agorgl avatar agorgl commented on July 19, 2024

Just tried it, still no luck.

from mpc.

orangeduck avatar orangeduck commented on July 19, 2024

Can you post your grammar in full? It could be in another part.

from mpc.

agorgl avatar agorgl commented on July 19, 2024

Here it is!

charsep      : "'" ;
strsep       : '"' ;

int          : /-?[0-9]+/ ;
char         : <charsep> (<specchar> | /[^']/) <charsep> ;
specchar     : /\\[ntr0']/ ;
string       : <strsep> /([\\]["]|[^"])*/ <strsep> ;
id           : /[a-zA-Z][a-zA-Z0-9_-?]*/ ;

mathoperator : ('+' | '-' | '*' | '/' | "mod") ;
booloperator : ('=' | "<>" | "<=" | ">=" | '<' | '>' | "and" | "or") ;

singletype   : "int" | "bool" | "char" ;
array        : <type> "[]"   ;
list         : "list" '[' <type> ']'   ;
type         : <singletype> | <list> | <array> ;

formal       : ("ref")? <type> <id> (',' <id>)* ;
header       : <type>? <id> '(' (<formal> (';' <formal>)*)? ')' ;

funcdef      : "def" <header> ':' (<funcdef> | <vardef> | <funcdecl>)* (<stmt> | <slcomment> | <mlcomment>)* "end" ;
funcdecl     : "decl" <header> ;
vardef       : <type> <id> (',' <id>)* ;

exprsimple   : <atom> | <int> | <char> | <string> | "false" | "true" | "nil" ;
expr         : "not" <expr> | "new" <type> '[' <expr> ']'
               | /nil\?/ '(' <expr> ')'
               | (<exprsimple> | '(' <expr> ')') (<mathoperator> <expr>)+
               | (<exprsimple> | '(' <expr> ')') <booloperator> <expr>
               | (<exprsimple> | '(' <expr> ')') '#' <expr>
               | ("head" | "tail") '(' <expr> ')' |  ('+' | '-') <expr>
               | <exprsimple> | '(' <expr> ')' | <id> ;

call         : <id> '(' (<expr> (',' <expr>)*)? ')' ;
atom         : <type> | (<call> | <id> | <string>) ('[' <expr> ']')+ | <call> | <id> | <string> ;
simple       : "skip" | <atom> ":=" <expr> | <call> ;
simplelist   : <simple> (',' <simple>)* ;

slcomment    : /%[^\r\n]*/ ;
mlcomment    : "<*" (<mlcomment> | /\*[^>]|[^*]/)* "*>" ;

stmt         : "return" <expr> | <simple> | "exit"
               | "if" <expr> ':' <stmt>+ ("elsif" <expr> ':' <stmt>+)* ("else" ':' <stmt>+)? "end"
               | "for" <simplelist> ';' <expr> ';' <simplelist> ':' <stmt>+ "end" ;

program      : /^/ <mlcomment>* <funcdef> <mlcomment>* /$/ ;

(Although as i said, i believe the problem occurs on these lines, because if i change the array definition in the workaround mentioned earlier everything works ok)

from mpc.

agorgl avatar agorgl commented on July 19, 2024

Just confirmed my suspision, i stripped down all the grammar to this:

singletype   : "int" | "bool" | "char" ;
array        : <type> "[]"   ;
list         : "list" '[' <type> ']'   ;
type         : <singletype> | <list> | <array> ;

program      : <type>;

And still infinite recursion.

from mpc.

orangeduck avatar orangeduck commented on July 19, 2024

Think I spotted it. The left recursion is between array and type:

array        : <type> "[]"    ;
list         : "list" '[' <type> ']'   ;
type         : <singletype> | <list> | <array> ;

If you are parsing an array then first you parse a type. If type fails to find a singletype or a list then again it will try to parse an array - which will kick off the process again. You need to factor this grammar somehow. Perhaps something like this:

list         : "list" '[' <type> ']'   ;
type         : (<singletype> | <list> | <array>) "[]"* ;

from mpc.

agorgl avatar agorgl commented on July 19, 2024

Its an interesting workaround, but the problem is that like this an array definition is interpreted like a type and not like an array, and that is not gonna help me in semantic analysis..

from mpc.

agorgl avatar agorgl commented on July 19, 2024

Is there any way in which we can see how it tries to parse the given input?

from mpc.

orangeduck avatar orangeduck commented on July 19, 2024

Sorry there currently isn't a way to see how mpc tries to parse the input, but essentially it just applies the rules of the grammar that are given and when it gets to optional rules (|) it will just try to parse each rule in turn.

There are various ways you can factor the grammar but you'll have to find one that gives the labels you want and doesn't contain left recursion. Essentially the problem is that you have the "[]" on the right hand side in your language - which is not going to work if you want array to somehow be a subrule of type. In fact it should be more like the other way around if it is on the right. A type should optionally have a number of "[]" on the end - and a type without that should be some kind of basictype or something which is a subrule of the more general type.

But since this isn't a bug in the library I'm going to close the issue. I hope you manage to find a way to structure the grammar that works.

from mpc.

agorgl avatar agorgl commented on July 19, 2024

Thank you for your help.

from mpc.

Related Issues (20)

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. 📊📈🎉

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google ❤️ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.