Questions tagged [parsers]

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

Filter by
Sorted by
Tagged with
3
votes
0answers
100 views

Unambiguous context-free language that can't be parsed in linear time by backtracking recursive descent?

Is there a context-free language that can be expressed with an unambiguous grammar but can't be expressed with a grammar that would result in linear-time backtracking recursive descent parsing? The ...
2
votes
1answer
2k views

Shunting Yard Algorithm extension and AST generation

Let me introduce you to my current project (that obviously yields the problem I face hence I post here). I am writing a so-called "compiler" for a simplistic language. I have already built a VM ...
0
votes
1answer
44 views

Can I mix LL and LR parsing?

I want to go RD parsing with Shunting Yard for expression (for the sake of easier operator precedences and less left-recusion), is that considered no-good because nobody did that before?
6
votes
2answers
304 views

any hope for a universal automatic parser?

Say you are a program, and you are given some source code but you don't know in what language, it can be C++/Java/Python/Lisp/... all you know is that it is highly structured and LR(1) parse-able, and ...
4
votes
1answer
376 views

Parsing CFLs (simulating PDA vs CYK algorithm)

We can simulate the PDA and parse the language with the following operations (vaguely): Read the input symbol and top of stack - $O(1)$ Check all the transition rules (must check all for non-...
2
votes
0answers
55 views

Correct bracketing check with rotate operation on position i

Given sequence (length $N$) of brackets like $($ and $)$. The task is to implement data structure which supports following operations: Check whether the sequence is correctly bracketed Rotate bracket ...
0
votes
1answer
129 views

Context Free Grammar for Try-Catch-Finally Statement and Throw

I am currently working on a problem that is asking me to write the grammar productions for the try-catch-finally and throw C# statements. It states that "you can assume that there are nonterminals "...
2
votes
1answer
1k views

White-space and comment by lexical analyzer

Lexical Analyzer mostly deletes comments and white-spaces. One example where I think Lexical Analyzer might not be discarding white-spaces is in Python language, as indentation has a important role in ...
5
votes
1answer
1k views

Check for balanced parentheses in an expression in log-space

Given an expression (a word in the one-sided Dyck language), I want to write a program to examine whether the pairs and the orders of “{“,”}”,”(“,”)”,”[“,”]” are correct in the expression. For ...
4
votes
3answers
980 views

Streaming parsing algorithms

A parser is a procedure which decides if an input belongs to a certain language and produces a witness in the form of a parse tree. Let a streaming parser be a parser which for any prefix $u$ can ...
0
votes
1answer
2k views

Conditions for LL(1) grammar

One of the conditions for A → α | β to be LL(1) grammar states that If β → ε in one or more steps then α doesn't derive any string beginning with a terminal in FOLLOW(A). Likewise If α → ε in one ...
1
vote
1answer
384 views

What is a “special sequence” in EBNF?

In Extended Backus-Naur Form (EBNF) there is one form called a "special sequence" which is surrounded by questions marks ?...? What does this mean?
0
votes
2answers
619 views

Proving that a CFG generates a language [duplicate]

Is a suitable way to prove that any given CFG generates (or not) any given language to draw its total language tree? What if the tree is infinite? What would then be a better way to prove that a ...
2
votes
1answer
208 views

Does my grammar contradict LL ⊆ LR(1)?

This answer claims that $ LL \subseteq LR \left( 1 \right )$ where $LL = \bigcup_k LL(k)$. But is this true? Is this grammar a valid counterexample? $ S \rightarrow a | Aaa $, $ A \rightarrow \...
0
votes
1answer
73 views

Is there any precedence for symbols for constructing parse trees? [duplicate]

I am wondering if some symbols such as the ones in propositional logic have precedence over others in drawing parse trees. For example, the sentence: p ∧ q → r, ...
6
votes
1answer
654 views

What would a formal grammar for a binary file format look like?

Binary structures often feature length specifiers; the parser is supposed to read them and then consume the specified amount of symbols. Because of this, the grammar is context-sensitive. What would ...
0
votes
1answer
33 views

Unsure about parse tree of PCFG

I'm new to build parse trees and I'm really unsure if I'm doing this right. So I have this example Grammar (S->Sa, S->aSa, S->a) and the word I'm parsing is simply aaaa. My solution would look like ...
1
vote
1answer
44 views

Why is particular token missing in LALR lookahead set?

I ran the following grammar (pulled from the dragon book) in the Java Cup Eclipse plugin: S' ::= S S ::= L = R | R L ::= * R | id R ::= L The items associated ...
1
vote
0answers
84 views

How do merged lookahead sets help LALR parse more grammars than SLR? [closed]

From what I have searched on Google so far, the only difference between LALR(1) and SLR(1) is that LALR(1) uses states with merged lookahead sets. One source says that LALR(1) won't run into shift-...
-2
votes
1answer
114 views

What's the step for build a SLR table for the following CFG? [closed]

(r1) E → E+T (r2) E → T (r3) T → T F (r4)T →F (r5) F → F∗ (r6) F → a (r7) F → b I am just doing the exercise on the workshop. I just knew how to the build the SLR state machine for this CFG. ...
1
vote
1answer
50 views

operator precendence grammar

According to this post https://stackoverflow.com/questions/28397767/computing-leading-and-trailing-sets-for-context-free-grammar while constructing operator precendence parser we have to create tabel ...
2
votes
2answers
90 views

Is the word problem of CFLs in NC?

Consider the membership problem for a context-free language. An instance of this problem can be described as pair $(G,w)$, where $G$ is a context-free grammar and $w$ is a string. Lets say I have a ...
1
vote
0answers
96 views

How can we avoid mistake in LL(1) parse tree?

I'm learning about LL(1) parse tree. We need to find first and follow in order to construct a LL(1) parse tree. Each and every ...
1
vote
1answer
2k views

Lookahead in LL(k) parsing

I'm having difficulty understanding what lookahead is $\mathrm{LL}(k)$ parsing. Does $k$ lookahead mean I consume $k$ symbols at a time and then process them? Any help is appreciated.
3
votes
2answers
391 views

Meta-grammar for context-free grammars

Formal grammars like regular expressions (REs) or context-free grammars (CFGs) specify languages, i.e. sets of strings over an alphabet. Grammars themselves can be seen as languages, e.g. the set of ...
4
votes
0answers
506 views

How does this left-associative recursive descent parser work?

For personal enlightenment, I'm trying to write a recursive descent parser for lambda calculus without abstraction, i.e., just identifiers and function application. The BNF grammar that describes the ...
1
vote
1answer
2k views

Need for an augmented grammar

The question is under the concept of LR parser. Suppose the original grammar is S->AA A->aA|b Is it necessary to add an additional rule S'->S to make it as augmented grammar? In short, I want to ...
-1
votes
2answers
695 views

I'm having trouble with Parse Trees

I am doing homework and I have the following problem: Consider the grammar: ...
0
votes
1answer
400 views

Is the given grammar LALR

We are given the following grammar. S-->AS/b A-->SA/a We have to tell if its LALR or not. As we all know that LALR is only minimization of CLR, So first I constructed the CLR parsing table using ...
0
votes
1answer
1k views

Need to remove indirect left recursion from CFG

I need to remove indirect left recursion from the following CFG: remove indirect left recursion from the following CFG. $$A → Ba| b$$ $$B → Cd | e$$ $$C → Df | g$$ $$D → Df | Aa | Cg$$ In the ...
0
votes
0answers
246 views

how to determine the action from the stack using the LR parsing tables?

I've been having a hard time wrapping my mind around the LR parsing table. Say I have the following table given the input action of id+id*id$ how does Stack ...
0
votes
2answers
97 views

Is the number of operators always one less than the number of values in an arithmetic Reverse Polish Notation expression with only binary operators?

Is the number of operators always one less than the number of values in an arithmetic Reverse Polish Notation expression with only binary operators? This question seems very trivial, but I don't know ...
1
vote
0answers
145 views

Upper bound of automaton states for SLR parsing

How do I tell, given a specific grammar, which is the upper bound for the number of states of a LR(0) or LR(1) automaton for its SLR parsing? My guess is that generating the canonical item collection ...
2
votes
1answer
598 views

How to treat $\epsilon$ and '$' in top-down predictive parsing (predict table)?

How to treat $\epsilon$ and '\$' in top-down parser using predict table? The construction of the predict table Given a product $X \rightarrow w$, row $X$ and column $t$ -Mark $X \rightarrow w$ ...
1
vote
1answer
873 views

Indirect Left recursion

I'm solving (indirect Left Recursion) for these production rules . S is the starting symbol. S -> Aa / a eq1 A -> Sb / b. eq2 Now I can do this in two ...
2
votes
0answers
266 views

How to find conflicts in LALR parser?

I have a LR analyser and I can't find out how to know whether the grammar is or is not LALR(1). I think that I have to merge states with the same rules. So I have to merge states: $2 - 12, 3 - 13, 4 -...
3
votes
1answer
849 views

How can I check that the language of one context-free grammar is a subset of a second context-free grammar?

Could you explain me, how can I check, that the language of first context-free grammar (G1) is a subset of the language of second context-free grammar (G2). G1 and G2 are two LL(1) grammars with ...
-2
votes
1answer
707 views

Basic idea behind error recovery in recursive-descent parsers

I see that modern SW basically dominated by recursive descent parsers. These parsers try grammar production and back track to an alternative one in case of failure. Suppose BNF is ...
1
vote
1answer
178 views

How to treat ϵ-productions in table-driven predictive parsing?

Here: https://www.cs.rochester.edu/~nelson/courses/csc_173/grammars/parsing.html in chapter Driver Procedure, it's shown how table-drive predictive parsing works. The predict table however can ...
0
votes
1answer
931 views

Trouble understanding how to create a grammar parse tree

I'm starting an online Computer Science class called Advanced Programming Languages, and the book asks me to create a parse tree and generate a grammar from it. Here are the exact instructions: To ...
0
votes
2answers
239 views

Is the language $L=\{a^nb^n\} \cup \{aa*\}$ DCFL?

Is the language $L=\{a^nb^n\} \cup \{aa*\}$ DCFL OR CFL? The author says $L$ is CFL, but I am able to generate a Deterministic PDA for the corresponding language. I am naive in this subject and hence ...
1
vote
3answers
1k views

Does precedence matter in constructing parse trees of arithmetic expressions for postfix notation?

Table 4 in Problem Solving with Algorithms and Data Structures's chapter on Infix, Prefix and Postfix Expressions gives the following examples: ...
0
votes
1answer
26 views

In top-down parser how do you match a product $A \rightarrow a_1 | a_2 | …$, $a_i$s terminals

One procedure for table-driven top-down parsing is given here: https://www.cs.rochester.edu/~nelson/courses/csc_173/grammars/parsing.html This gives for matching the input the lines: ...
4
votes
2answers
537 views

What is the point of delimiters and whitespace handling

I see that language specifies reserved words, delimiters and whitespaces in the lexer section. Are delimiters just like reserved identifiers in the punctuation space or they have additioinal function ...
0
votes
2answers
65 views

Is C → A B C | A left-factorizable?

$$C \to A B C \mid A$$ Obviously has the same FIRST(C) for the both productions. But how can this be left-factorised? Tried: $$C \to A B C'$$ $$C' \to A C \mid \varepsilon$$ The FIRST sets are ...
0
votes
1answer
121 views

Cocke-Younger-Kasami (CYK) algorithem for the word $baabb$

With the context-free grammar in Chomsky's form:$$S\to BA|AC|b\\A\to AA|AB|CC|a\\B\to AS|BB|CA\\C\to AB|SS|b$$ I need to: run the CYK (Cocke-Younger-Kasami) algorithm and decide if I can ...
0
votes
1answer
120 views

Are parser combinators equivalent to scannerless parsing?

From what I can see, parser combinators are equivalent to scannerless parsing. I do not see this stated in implementations of scannerless parsing page, nor in the parsing combinators page, neither in ...
-2
votes
1answer
245 views

Automata vs Earley parsing? [closed]

If the language is implementable as mere DFA (i.e. it's a regular language), then why would one need a parsing algorithm such as Earley. Regular languages are a subset of context-free languages, but ...
0
votes
1answer
171 views

In NLP, does the lexer have to tag the tokens before the parser?

In NLP, does the lexer have to tag the tokens before the parser? I.e. does the lexer have to classify the tokens to morphological categories before the parser? I'm thinking yes, but is this also the ...
1
vote
1answer
35 views

Duplicating the quotation marks in in the quotation-mark enclosed strings

There is such a grammar string_literal ::= " { graphic_character } " The double-quotes that you see must appear in the user program and curly braces mean "any ...