Comments (10)
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.
Just tried it, still no luck.
from mpc.
Can you post your grammar in full? It could be in another part.
from mpc.
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.
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.
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.
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.
Is there any way in which we can see how it tries to parse the given input?
from mpc.
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.
Thank you for your help.
from mpc.
Related Issues (20)
- Implementation of `mpcf_all_free` not seen in mpc.c HOT 1
- In theory: Can MPC parse C? HOT 2
- scan coverity findings HOT 1
- Add support for arm64 architecture. HOT 4
- CMakeLists.txt suggestion HOT 6
- Release: GNU Guix
- Segmentation fault and timeout occur at mpca_lang_st() HOT 1
- Does the order of definitions matter in languages? HOT 2
- Mix parsers and AST HOT 3
- Greedy matching causes token matching issue HOT 2
- What about MPC now? HOT 1
- "-static" does not work on newer MacOS due to crt0
- make install does not work on newer MacOS (install command/folders)
- dependency errors issue HOT 9
- shared state and multi-threaded use HOT 2
- parser for """long string""" ? HOT 2
- Make include guards unique
- Completion of error handling
- memory leak in mpca_lang function
- Unicode and regexs etc HOT 1
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
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.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from mpc.