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.

Filter by
Sorted by
Tagged with
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'...
Chappi's user avatar
  • 1
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 > ...
yes12345's user avatar
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 | ...
phuck's user avatar
  • 23
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 ...
MannBell's user avatar
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> &...
Dagun's user avatar
  • 41
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 ; ...
Lorenzo's user avatar
  • 571
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....
Corey Hodges's user avatar
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 ...
rickhg12hs's user avatar
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 ...
TF.Ryan's user avatar
  • 53
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 ...
xpt's user avatar
  • 19.8k
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 ...
Irodi's user avatar
  • 1
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 ...
user3699192's user avatar
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 ...
Jonathan1609's user avatar
  • 1,779
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 ...
Khanh Nguyen's user avatar
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 ...
raf_135711's user avatar
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 ...
JFreeman's user avatar
  • 974
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 >= ...
Károly Tóth's user avatar
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 ...
Lance's user avatar
  • 74.4k
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 ...
Lucy's user avatar
  • 1
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 &...
IC_'s user avatar
  • 1,573
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 ...
Omri. B's user avatar
  • 325
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 ...
Omri. B's user avatar
  • 325
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 ...
Aphrontos's user avatar
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 ...
justForFun's user avatar
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?
lzcmz's user avatar
  • 1
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 -> ...
jvinkovic's user avatar
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 ...
rempas's user avatar
  • 123
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 ...
user200783's user avatar
  • 13.6k
-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 ; ...
SRSR333's user avatar
  • 192
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 ...
AndreasS's user avatar
  • 315
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 ...
AM429's user avatar
  • 306
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. ...
AM429's user avatar
  • 306
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 ...
xilpex's user avatar
  • 3,047
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 ...
xilpex's user avatar
  • 3,047
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: <...
Touloudou's user avatar
  • 2,019
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> <...
Harshini Aitharaju's user avatar
-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>...
Ikechukwu Anude's user avatar
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:...
user avatar
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 ...
gladiesgoodluck's user avatar
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 ...
Daniel Decker's user avatar
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 ...
Monolith's user avatar
  • 1,067
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 ...
Alex Tudor's user avatar
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 ...
clickedok's user avatar
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: ...
Monolith's user avatar
  • 1,067
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 ...
Ben Nutter's user avatar
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",...
GameFromScratch's user avatar
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 ...
Briko's user avatar
  • 19
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 ...
Joshua Wise's user avatar
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 ...
Zachary's user avatar
  • 27
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 ...
user avatar

1
2 3 4 5