Questions tagged [parsers]

Questions about algorithms that decide whether a given string belongs to a fixed formal language.

Filter by
Sorted by
Tagged with
2
votes
1answer
30 views

Convert a dfa to rule for a asterisk case

Here is a simple but very common grammar rule case in EBNF format, the Statements is a none terminal symbol and Statement is ...
1
vote
0answers
26 views

Parse algebraic expression into a list of operations

Given algebraic expression in a string, I want to split it into a list of operations for building a parallel binary tree. For example, I'm trying to convert expression such as: ...
0
votes
0answers
8 views

An RDP Rule consumed a token and the other rule can't parse the sentence

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: ...
1
vote
1answer
42 views

How to write a non-ambiguous grammar for the syntax of lambda calculus?

I tried to write a non-ambiguous grammar for lambda calculus, but it does not really work. The recursive-descent parser is easy to write though. I googled but all results I collected so far are ...
0
votes
0answers
12 views

Tips on making a grammar LL(1)?

So I currently am given the following grammar, and I have to make it LL(1). To do this, I need to remove ambiguities, eliminate left recursion, and left factor if necessary. But looking at this, it's ...
1
vote
0answers
26 views

Should a lexer (tokenizer) handle unknown operators?

I have a list of supported operators, my question is whether the lexer should just yield the token for the operator or raise a syntax error in case that particular operator (let's say "?") ...
0
votes
1answer
20 views

LALR lookahead is wrong, why?

I am studying LALR(1) parser and I have this question: Consider the following Grammar S - > V = E E - > F | E+F F - > V | int | (E) V - > id Construct the LALR(1) parsing table for this ...
1
vote
1answer
38 views

set theory with RegEx on fen strings (or another parser)

how can you find if a regex call is a subset of another regex call on an predictable set of data I have a string (chess Forsyth–Edwards Notation (FEN) string...
0
votes
1answer
29 views

Convert regex pattern to LL1 parser

Background: I'm trying to solve this leetcode problem: regular-expression-matching. My approach is to implement a LL(1) parser generator, might be overkilling for this problem but it's just a brain ...
1
vote
0answers
24 views

Handling infinite loop in implementation Pushdown Automaton (PDA)

I've got a basic implementation of a Pushdown Automaton which recursively checks the rules of a grammar in CNF to find whether a given input string is accepted or not, and it can also count the number ...
0
votes
1answer
30 views

Why does bottom-up parsing of right-recursive grammars require unbounded O(n) stack space?

I keep reading that while bottom-up parsing of a left-recursive grammar can be done in constant O(1) stack space, for a right-recursive grammar, we have to push the entire input stream onto the stack ...
1
vote
1answer
84 views

Hierarchy of parser grammars vs Chomsky hierarchy of grammars and the comparsion of the language acceptance power of each parser grammar

While reading the text Modern Compiler Implementation in C by Andrew Appel I came across the hierarchy of grammar given below. The above diagram is very helpful in understanding the correlation among ...
1
vote
0answers
23 views

Condition of LL(3) grammer

To find out whether a grammar G is LL(1) or not, we test this condition among other conditions, "If whenever A -> alpha | beta are two distinct productions ...
1
vote
2answers
98 views

Are parse trees always produced?

When my instructor taught compiler construction he explained all the phases of compiler and their working nicely. But when I read online here, at last line it is written that Parse trees are not ...
0
votes
0answers
46 views

Why the grammar is not (LL1)?

Why the grammar is not (LL1)? (e is the epsilon) $$S \to a A \mid b B \mid a C c $$ $$A \to a A \mid a a A \mid e $$ $$B \to c C \mid D \mid e $$ CHOICE 1: The grammar is Left-Recursive (LR) CHOICE 2: ...
0
votes
1answer
64 views

How are lexical tokens produced

I am studying Compiler Design. The instructor told us that when a program is given to lexical analyzer it find all tokens then a symbol table is created and it is updated at every phase accordingly, ...
1
vote
1answer
57 views

More efficient way to parse array into binary search tree

Let's assume I have array which I need to parse into binary tree ...
0
votes
1answer
20 views

How would you specify a grammar that can parse letters separated by single underscores?

In JavaScript, let's say, it is easy to build a string intermixed with single underscores by just joining the string parts. ...
0
votes
0answers
27 views

What's the point in a symbol table or AST when all the information is available in the parse tree?

This is a question I haven't worked out the answer to yet probably because I haven't done any hands on middle end compiler design. I feel like the explanation of the true purpose of an AST were ...
1
vote
1answer
46 views

Can given grammar be parsed using recursive descent?

I have this Grammar below: ...
1
vote
0answers
12 views

How do bottom up parser evaluate things that need an inherited attribute?

I learned that Bottom up parsers use only synthesized attributes to evaluate semantics. Which makes sense considering that it would be very hard to evaluate an inherited attribute in bottom up ...
1
vote
1answer
31 views

Parse forest from an ambiguous grammar

Parser-generators like nearleyjs can return a parse forest instead of a parse tree. Since not all input may result in a parse forest (eg, the input may exercise ...
0
votes
1answer
72 views

Grammar for $\{a^n b^n c^m d^m \mid n \geq 1, m \geq 0\}$

I'm trying to understand how the construction of simple grammars works. In my textbook, there's the following example I am supposed to find a grammar for: Let $L_1= \{a^n b^n c^m d^m \mid n \geq 1, m ...
0
votes
2answers
56 views

A state machine that is either DFA or NFA: is it possible?

I am studying Crafting Interpreters, and although I understand the responsibility of the Scanner (or Lexer), I still cannot understand if it is a deterministic finite automaton or non-deterministic ...
0
votes
1answer
42 views

BNF syntax for a recursive function?

I'm to write a syntax that will allow for a recursive function, i.e. f(x) = if x == 0 then x else f(x+1) Here's one attempt at creating the grammar: But I don't ...
1
vote
0answers
40 views

Generating a recursive descent parser for grammar having Kleene star

From what I have been taught, I cannot use left-recursive, nondeterministic, or ambiguous grammars in recursive descent parsers. So, here is the grammar: \begin{align} &E \to E+T \mid T \\ &T \...
1
vote
1answer
54 views

Would a parser for this left-recursive grammar require infinite input?

I am considering this left recursive language grammar production rule: Expr = Expr, "a" ; As a production rule, I believe that this can be used to ...
0
votes
0answers
23 views

Parsing HTML from HTTP vs HTTPS websites

Are there any alternative steps to receiving and then parsing the HTML of an unsecured site (HTTP) vs a secured site (HTTPS)? I am asking as I learnt that there is encryption involved in the HTTPS ...
0
votes
1answer
38 views

How is $A.in$ an inherited attributed in $2nd$ production in $(1) S \rightarrow A_1A_2\{ A_1.in := 1; A_2.in := 2 \}(2) A\rightarrow a\{print(A.in)\}$

Below is an excerpt from the Red Dragon book. $$(1) \quad S \rightarrow A_1 \quad A_2 \quad\{ A_1.in : = 1;\quad A_2.in : = 2 ;\}$$ $$(2) \quad A \rightarrow a \quad \{ print(A.in) \}$$ We find that ...
0
votes
1answer
42 views

L-attributed definitions include all syntax-directed definitions based on LL(1) grammars

I was going through the text Compilers: Principles, Techniques and Tools by Ullman et. al where I came across the following claim: L-attributed definitions include all syntax-directed definitions ...
1
vote
1answer
46 views

In syntax-directed definition, terminals are assumed to have synthesized attributes only, definition doesn't provide any semantic rules for terminals?

I was going through the text Compilers: Principles,Techniques and Tools by Ullman et. al. where I came across the claim in the question by authors. Below is the definition and following it is the ...
0
votes
1answer
17 views

$\text{"The error entries in the goto table are never consulted"}$ - intuitive explanation of the above claim with respect to $LR$ parsing tables

I was going through the text : Compilers: Principles, Techniques and Tools by Ullman et. al where I came across a claim: $\text{"The error entries in the goto table are never consulted"}$ I feel ...
1
vote
0answers
39 views

Understanding the concept of "Viable Prefixes"

I was going through the text: Compilers: Principles, Techniques and Tools by Ullman et. al where I came across the concept of viable prefix and I faced some difficultly in grasping the concept. So I ...
0
votes
0answers
265 views

In shift reduce parsing why the handle always eventually appear on top of the stack and never inside?

I was going through the text Compilers: Principles, Techniques and Tools by Ullman et. al where I came across the excerpt where the authors try to justify why stack is the best data structure of shift ...
2
votes
0answers
23 views

Generating an "approximate" grammar

This is my first time posting here, so I hope I'm on topic. I have a table of natural-language data of the form ...
0
votes
0answers
23 views

Why can't I evaluate this L-Attributed SDD with a pre-order traversal?

My powerpoints for a compiler class says "an L-Attributed SDD can be evaluated with a pre-order (root, left, right) traversal", and to be L-Attributed the nodes need to have either ...
0
votes
1answer
33 views

CYK algorithm in theory of computation

For any context free grammar, there is a parser that takes atmost n^3 time to parse a string of length n. Doubt: I marked it false in a national level exam.I think it should be any null-free context ...
2
votes
0answers
22 views

Unparsing an operator grammar in the face of ambiguity

I'm using the grammar scheme of Danielsson and Norell ("Parsing Mixfix Operators"). The short version is: user defined mixfix operators such as _+_ or <...
2
votes
1answer
49 views

How is `y λx.x y` parsed using the standard pure untyped lambda calculus conventions?

How would the following term in the pure untyped lambda calculus be parsed: y λx.x y The relevant conventions listed on https://en.wikipedia.org/wiki/...
-1
votes
1answer
38 views

Compilers: how to find first and follow sets?

I sort of know how to solve the problem but I am not sure how to do it in a systematic way. Could someone provide a step-by-step solution especially for the follow set one? Thanks!
1
vote
1answer
50 views

How to handle L-attributed SDDs with LR parsers

I've read Chapter 5, Syntax Directed Translation, of the Dragon Book but am still unable to understand the following related points: How to handle L-attributed SDDs in an LR grammar when using a tool ...
0
votes
1answer
19 views

Compilers: How to see "the number of grammars where there exists a string that has at least two different left-most derivations"?

Could someone tell why "G1 and G3 are ambiguous" and how to see whether a string has at least two different left-most derivations in general?
0
votes
0answers
21 views

I am trying to design an LL(1) Parser that accepts T = {a, b *, +, ?, E, U, (, ) }

I am trying to design an LL(1) Parser that accepts regular notation where 'E' represents epsilon, and 'U' represents "or" like ' | '. So far I made one that accepts T = { a, b, *, +, (, ), E}...
0
votes
1answer
125 views

Computing FOLLOW sets of left recursive grammar

Left recursive ambiguous expression Grammar: $E \rightarrow E+E \mid E*E \mid (E) \mid \mathbf i\mathbf d$ I tried computing FIRST and FOLLOW sets of both left recursive grammar and after ...
0
votes
0answers
32 views

What is the most commonly used/ most practical method to parse context sensitive languages?

what is the most commonly used / most practical method to parse CSLs ? By "most practical" I mean Not too theoretical but in opposite to that, with practical usecases Not too complicated (...
5
votes
1answer
135 views

Why is XML hard to parse?

I was chatting with a friend about my love/hate relationship with XML. He made the comment that, "xml is broken primarily because parsers for recursive self-defined document are basically ...
1
vote
0answers
24 views

Is there a direct way to obtain the RE for the handle-finding DFA of a grammar?

LR parser for a (CFG) grammar uses a handle-find automaton (which is a DFA) to find the handles. Such automata can be constructed by computing the canonical collection of sets of LR(0)/LR(1) items. Is ...
2
votes
1answer
116 views

Linear Grammar in less than cubic time

I have a linear grammar $G$ and a string $s$. $G$ is is not limited to right or left linear only but rather has a mix of rules of both types. Is there an algorithm to determine whether $s \in L(G)$ ...
1
vote
1answer
65 views

CYK - finding the closest word accepted

Let's say I have a context-free grammar G and a string S. The normal CYK algorithm outputs that s can not be build using G. How would I find the closest String S' that can be build using G?
1
vote
1answer
209 views

What does "lookahead" refer to?

I keep hearing about lookahead parsers, LL parsers, LR, LALR, etc... but no clear explanation behind the etymology of this word. What does "lookahead" refer to? How does this relate to LL, ...

1
2 3 4 5
9