Questions tagged [recursive-descent]
Recursive Descent Parser is a kind of top-down parser built as a set of recursive procedures each implementing a production rule of the grammar.
206
questions
0
votes
0
answers
35
views
Why is my Recursive Descent Parser not parsing an empty string?
coding gods really wondering if someone can help with this little ol issue, this is what I've currently got it is a Recursive Descent Parser that takes Jack code and translates it into a parse-tree, I'...
0
votes
0
answers
25
views
What are the criteria for determining if a language can be parsed using recursive descent parsing?
How do i know if a language can be parsed by recursive descent parsing?
For example, how would i go about determining whether this language can be parsed in that manner:
Language = { s^p r^q | p > ...
0
votes
1
answer
61
views
languages parsed with recursive descent
I was wondering what makes languages possible to be parsed with recursive descent. for example we have 5 languages over {x,y,r}:
A = { x^n y^n | n <= k }
B = { x^n y^k | n > k }
C = { x^k y^n | ...
1
vote
0
answers
30
views
Context Free Grammar clarification
I created the following grammar for a minishell, but i realized that the parser never goes to command_p, it only stays at cmd_prefix.
Can somebody please clarify for me since i've seen a similar ...
0
votes
1
answer
164
views
Recursive descent parser from BNF grammar in java
I need to make a recursive descent parser that follows the grammar
<program> → <statements>
<statements>→ <statement> | <statement><semi_colon><statements>
&...
0
votes
1
answer
33
views
Removing left recursion from JSF*ck grammar rules
I am trying to figure out a JSF*uck grammar. I read the actual JavaScript grammar here and only took the grammar rules that were relevant to JSF*ck and got this:
Expression: AdditiveExpression ;
...
1
vote
1
answer
175
views
How can I transform this into a recursive descent parser
My code is a follows (this code 100% works, it just doesn't use recursive descent)
import java.awt.Component;
import java.awt.FlowLayout;
import java.awt.GridLayout;
import java.io.File;
import java....
2
votes
1
answer
184
views
MongoDB javascript `"$function"` not returning expected value in mongoplayground.net
N.B.: This is the first javascript function I've written. My question is inspired by another question inquiring about recursive descent within a MongoDB document.
I tried the function on jsfiddle.net ...
0
votes
0
answers
89
views
Verifying if an expression conforms to restrictive context-free grammar
I'm trying to write a parser that accepts a toy language for a software project class. Part of the production rules relevant to the question in EBNF-like syntax is given here (there's way more ...
1
vote
0
answers
276
views
Converting W3C's EBNF to BNF
Following up on
Converting EBNF to BNF, which has a rule of:
From EBNF to BNF
For building parsers (especially bottom-up) a BNF grammar is often better, than EBNF. But it's easy to convert an EBNF ...
0
votes
0
answers
98
views
How to make recursive descent parsing recognise expressions
I am making a graphing calculator and the issue I am having is finding a way to take in inputs like sin(90) and run my function for sin that I coded into another file.
I am using a recursive descent ...
0
votes
0
answers
176
views
Types of Top down parsers
I want to clearly classify top down parsers. After reading lot of resources, i am connecting the dots.
I concluded following -
There are 2 types of top down parsers -
One that uses backtracking
...
0
votes
1
answer
75
views
The token was already consumed by another rule, Can't parse the token again
I am constructing an LL(1) parser (Recursive Descent Parser) and I need to parse the sentence a = 3, I have two procedures to match that rule: parse_assignment and parse_binary_operator,
each function ...
0
votes
2
answers
251
views
Recursive-descent parser
The question is to write a recursive-descent parser for a language that contains sentences of form w+w', in which w is an arbitrary string of lowercase chars, w' is the reverse of w, and + the plus ...
1
vote
1
answer
222
views
K&R dcl program detects almost nothing
I've been stuck with the dcl program from chapter 5.12 in K&R C. It is basically a program which accepts a C variable/function/table declaration and prints a description of it in English. It works ...
0
votes
1
answer
41
views
Invalid grammar for a top-down recursive parser
I am trying to create grammar for a naive top-down recursive parser. As I understand the basic idea is to write a list of functions (top-down) that correspond to the productions in the grammar. Each ...
0
votes
1
answer
117
views
Realize precedence climbing in Haskell
I am trying to realise precedence climbing in Haskell, following this specific algorithm:
compute_expr(min_prec):
result = compute_atom()
while cur token is a binary operator with precedence >= ...
2
votes
2
answers
930
views
How to construct tree pattern matching algorithm in JavaScript?
Okay this is a bit of an involved question, but tl;dr it's basically how do you parse an "actual tree" using a "pattern tree"? How do you check if a particular tree instance is ...
0
votes
0
answers
79
views
Recursive descend parser for evalutating math expressions throws an error and I do not how to fix it
I'm new here and have a generall question. I'm trying to create a recursive descent parser for the evaluation of mathematic expressions, and the parser I have crafted until now also works very good ...
0
votes
2
answers
61
views
Please, help me to understand parsing trees example from craftinginterpreters.com
I'm trying to build a C compiler from scratch. Googling took me to the https://craftinginterpreters.com/ site. There are a lot of explanations how source code parsers work in detail. I've reached &...
0
votes
1
answer
437
views
Recursive descent parser - dealing with closing brackets
I'm trying to build a recursive descent parser that builds an AST as it goes. The language is fairly simple;
x >/</= y #x, y can be any letter/number, matched by regex.
Then, AND/OR with ...
0
votes
1
answer
143
views
StringTokenizer replacement in Java
I'm trying to write a recursive descent parser. I need a method that converts the string to a stream, so I can use a next method. Everywhere I read, it says that StreamTokenizer is outdated and ...
0
votes
0
answers
60
views
An erroneous successful parsing in a recursive descent parser
I have the following code. It's a recursive descent parser with backtracking.
/*\ /*\
|*|--------------|*|
|*| Grammar: |*|
|*| A -> ( A ) B |*|
|*| | [ A ] B |*|
|*| | n B ...
2
votes
1
answer
458
views
Parsing nested parentheses in F# using recursive descent
I'm trying to make a recursive descent parser in F#. I looked at http://www.fssnip.net/bM but this type of parser uses a string instead of a list.
I'm struggling with parsing parentheses, and ...
0
votes
1
answer
57
views
Does a Recursive Predictive Descent Parser NEEDS to construct a complete syntax tree and store in memory?
I've been thinking and a question has arisen. Does this type of compiler really need the complete syntax tree in memory?
0
votes
1
answer
213
views
Cannot get LL(1) form of grammar for recursive descent parser
I have grammar:
S -> bU | ad | d
U -> Ufab | VSc | bS
V -> fad | f | Ua
To contruct recursive descent parser I need LL(1) form.
Best I got is:
S -> bU | ad | d
U -> fY | bSX
Y -> ...
1
vote
0
answers
158
views
Eliminating left recursion from function call parsing
First of all, I know there are a lot of answers and resources already available regarding this topic. However, I'm having a really hard time understanding the grammar notation that is often used in ...
0
votes
1
answer
159
views
How can I simplify a recursive-descent parser?
I have the following simple LL(1) grammar, which describes a language with only three valid sentences: "", "x y" and "z x y":
S -> A x y | ε .
A -> z | ε .
I have ...
-1
votes
1
answer
47
views
Parsing procedure calls for a toy language
I have a certain toy language that defines, amongst others, procedures and procedure calls, using EBNF syntax:
program = procedure, {procedure} ;
procedure = "procedure", NAME, bracedblock ;
...
1
vote
2
answers
278
views
Parser/Grammar: 2x parenthesis in nested rules
Despite my limited knowledge about compiling/parsing I dared to build a small recursive-descent parser for OData $filter expressions. The parser only needs to check the expression for correctness and ...
0
votes
1
answer
520
views
Recursive descent Parser: infix to RPN [2]
this the continuation of me trying to make a recursive descent parser--LL(1)-- that takes in infix expressions and outputs RPN. Here is a link to my first question to which @rici did an amazing job of ...
0
votes
1
answer
870
views
Recursive descent: infix to postfix conversion repeating operators
We recently learned about converting infix to postfix using stacks during our programming course at uni. And I have meaning to write my parser for a while, so I decided to it using recursive descent. ...
0
votes
1
answer
493
views
How does gcc/clang parse c++ if it can't be parsed by a LR(1) parser?
GCC/Clang are handwritten parsers. I read a post saying that C++ can't be parsed by an LR(1) parser (Why can't C++ be parsed with a LR(1) parser?). If so, how come GCC/Clang are handwritten ...
0
votes
0
answers
255
views
LALR parser being slower than recursive descent parser
Recently I wrote a (highly optimized) LALR(1) parser (that could handle ambiguous grammars) and supplied it a very ambiguous grammar. After that, I wrote a recursive descent parser for the same ...
2
votes
0
answers
170
views
How to rewrite this grammar for LL(1) parsing?
I am trying to write a top-down recursive-descent parser for a small language, and I am facing some issues with the assignment statements. Here is the grammar from the language specifications:
<...
0
votes
0
answers
352
views
Writing a recursive descent parser with nested if-conditions
I am writing a recursive descent parser for parsing a specific grammar, and I have to do the nested if/else in that grammar.
The grammar is as follows:
<statement> ::= if <cond> <...
-1
votes
1
answer
255
views
Accepting an Equal Sign using Recursive Descent Parsing in C
I am currently trying to build a recursive descent parser that parses assignment statements such as a = 4 + b. The grammar looks as follows
<stmt> → id = <expr>
<expr> → <term>...
1
vote
1
answer
108
views
How to write code for part of a recursive descent parser? [duplicate]
I'm looking for an answer to this Stack Overflow question: Can somebody walk me through what this question is trying to ask of me?
It asks to do the following, as the person who replied to it explains:...
0
votes
1
answer
47
views
Partition the upper part for the given key
I would like to implant recursive search using python, it will partition the upper part for the given key
example: list[2, 4, 6, 9, 10]
for the key is 6 case, the return index is 3
for the key is 4 ...
1
vote
1
answer
107
views
Can somebody walk me through what this question is trying to ask of me?
The following programming languages question seems really unclear and what it wants me to do is not obvious to me, could somebody help me to understand it?
The question:
Implement part of a ...
6
votes
1
answer
967
views
Difference between a PEG and recursive descent parser?
I have recently come across PEG parsers, and Guido van Rossum's article on PEG parsers and how to construct them. That article talks about "PEG" parsers but internally it looks exactly like ...
0
votes
0
answers
160
views
What About Abstract Syntax Tree Recursivity In Javascript?
I am trying to build a compiler in javascript and until now I've managed to build a lexer that creates tokens based on input:
= Test Input (with optional semicolon):
data myVariable = 4
data ...
2
votes
1
answer
1k
views
Understanding this implemented recursive-descent parser in Haskell
I had an assignment problem were I had to parse a tokenized prefix calculator notation on a pre-defined AST. We were given a pretty complete algorithm for parsing (we had to add some stuff).
The ...
2
votes
1
answer
368
views
Infinite recursion for parsing arithmetic expressions using a recursive descent parser
I am trying to create my own recursive descent parser in python, but when my parser runs into a rule concerning arithmetic expressions, it surpasses the python recursion limit. Here is the grammar:
...
0
votes
1
answer
108
views
Recursive descent parser that counts the number of 'a' and 'b' characters not counting correctly
I'm writing a simple recursive descent parser that takes standard input and counts the number of 'a' and 'b' characters. The grammar for this is as follows:
S -> A B '\n'
A -> a A | empty
B -> b B ...
3
votes
0
answers
193
views
JsonPath SelectToken not working for recursive structure
I have the following JSON on which I want to get specific values using SelectToken -
{
"Result": {
"Id": "knownvalue0",
"Name": "Level0",
"Children": [
{
"Name": "Level1",...
0
votes
2
answers
391
views
How to code nextToken() function for a descent recursive parser LL(1)
I'm writting a recursive descent parser LL(1) in C++, but I have a problem because I don't know exactly how to get the next token. I know I have to use regular expressions for getting a terminal but I ...
4
votes
1
answer
529
views
How do parsers handle generic type parameters?
I'm writing a recursive decent parser for an imaginary programming language. It's a C-style language with common operators like ==, <, >, <=, and >=, and it also features generic functions (like ...
1
vote
1
answer
152
views
Recursive Descent Parser Should Error on Repetitive Letter Terminals
Primary question: How can I update my recursive descent parser for propositional logic (written in JavaScript) so that strings like "p~" and "pp" will return an "Invalid" message?
I am very new to ...
0
votes
1
answer
319
views
Given a recursive descent parser, how should I modify it for Syntax Analysis?
I have just finished coding a recursive descent parser for C Minus that simply prints "ACCEPT" if the input text file can be parsed or "REJECT" if not. I have a function for each rule in the grammar ...