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
62 views

Tokenizer and complex operators

I'm trying to create simple tokenizer to transform following (only part shown) search expression to tokens word1 near(1) word2 where word1, word2 are some words ...
2
votes
1answer
964 views

If a parser can parse a non-deterministic grammar, is the parser non-deterministic?

I've written a recursive-descent parser generator, and I'm trying to classify it (call me a cowboy coder if you must). According to wikipedia, S → 0S0 | 1S1 | ε, ...
13
votes
6answers
2k views

Does an abstract syntax tree have to be a tree?

Does the output of a parser have to be a tree or could it also be general graph? Moreover, is there any existing language or a plausible one that uses general graphs representation instead of trees ...
0
votes
1answer
44 views

$FIRST_k$ set — is algorithm given by Aho&Ullman correct?

I am writing this, because no matter how I look at the algorithm I see an error :-) Aho & Ullman in "Theory of Parsing, vol.1" (pp. 357-359) described the algorithm for building $FIRST_k(A)$ set ...
0
votes
1answer
122 views

What is a preterm parser?

I am working with HOL-Light parser and keeping seeing references to preterm parser. What is a preterm parser? The most informative statement I find is from the HOL-Light reference for the ...
2
votes
1answer
796 views

How to prove formally that grammar isn't LR(1)

I want to prove that grammar $$ \begin{cases} S'\rightarrow S\\ S\rightarrow aSb ~|~ A\\ A\rightarrow bA~|~b \end{cases} $$ isn't $LR(1)$. I've constructed parser table and got Shift-Reduce conflict. ...
6
votes
1answer
3k views

Parsing a string with LR parsing table

Me and my friends are studying for an upcoming test and this exercise is one of the harder ones for us. We have been trying to solve it and we have been looking at similar exercises, the problem is ...
2
votes
3answers
257 views

Weak Precedence Grammar and Parsing

I am studying parsing, i.e. bottom-up parsing. it is said that there some rules which are used by weak precedence grammar. What does weak precedence grammar mean? What about precedence relation? Any ...
2
votes
1answer
216 views

Negative lookahead in LR parsing algorithm

Consider such a rule in grammar for an LR-family parsing generator (e.g YACC, BISON, etc.): Nonterminal : [ lookahead not in {Terminal1, ..., TerminalN} ] Rule ; ...
9
votes
2answers
9k views

Two-State Turing Machine for Parenthesis Matching

In college we have been learning about theory of computation in general and Turing machines more specifically. One of the great theoretical results is that at the cost of a potentially large alphabet (...
6
votes
3answers
123 views

For regular languages A and B, determine whether B might match early in (A B)

I have two regular languages A and B, and I want to determine whether there is any pair of strings, a in A and b in B, such that (a b) is a prefix of a string in (A B) and the left-most ...
3
votes
1answer
285 views

Lookahead set: Determining minimum $k$ such that $G$ is a strong $LL(k)$ grammar

How do we determine minimum $k$ such that $G$ is a strong $LL(k)$ Grammar Like for grammar $G$ with the following rules $S\rightarrow aAcaa \mid bAbcc,A\rightarrow a \mid ab \mid \epsilon$
4
votes
2answers
254 views

Priority in formal grammar

From my recitation class, I have the following exercise: $\mathrm{EXP} = 0 \mid 1 \mid b \mathrm{EXP} \mid \mathrm{EXP} a \mid \mathrm{EXP} m \mathrm{EXP}$ The above grammar is ambiguous. ...
10
votes
1answer
324 views

Shift-resolve parsing - questions

I've recently came across a paper describing the parsing technique mentioned in the title. Unfortunately, the terminology used in said paper is somewhat beyond my comprehension, so I've been ...
3
votes
1answer
47 views

How to define at least one occurrence of a string between two tokens in bottom up LALR(1) parser grammar

I am trying to define a non terminal symbol in a LALR(1) grammar (with CUP parser). It is requested that ...
1
vote
1answer
999 views

Facebook Hackercup 2013: Balanced Smileys

On Facebook HackerCup 2013, they asked the following question: Your friend John uses a lot of emoticons when you talk to him on Messenger. In addition to being a person who likes to express ...
2
votes
1answer
241 views

Regular vs LALR(1): what is faster

Supposing we have two grammars which define the same languge: regular one and LALR(1) one. Both regular and LALR(1) algorithms are O(n) where n is input length. Regexps are usually preferred for ...
5
votes
1answer
11k views

What are handles in parsing?

I have read a few algorithms for $LR(k)$ parser, in which there is a frequent mention of selecting a handle from the grammar given. For example, one document said - "the essence of LR parsing is ...
4
votes
3answers
604 views

Is this grammar really LL(1) while not being LR(1)?

$S \rightarrow S$, $L(G) = \{\}$ LL(1) analysis: We estabilish $FIRST(S)$ to be empty and $FOLLOW(S)$ to be $\{\$\}$. $FIRST(S)$ doesn't contain ε, so the parse table looks like this: ...
2
votes
0answers
578 views

Parsing family of grammars, determine if LR(k)

Consider the family of grammars $G_n,~n\geq2$. $$S \rightarrow A_ib_i~,~for~~1\leq i \leq n$$ $$A_i \rightarrow a_jA_i~|~a_j~,~for~~1 \leq i,j \leq n~~and~~i \neq j$$ where multiple alternative right ...
3
votes
1answer
168 views

LL grammars and left-recursiviity

Why LL(k) and LL(∞) are incompatible with left-recursion? I understand that a LL(k) language can support left-recursivity provided that with k-overahead tokens can be resolved any ambiguity. But, with ...
2
votes
3answers
513 views

Example of a parsing/rewriting system?

I am studying formal languages and playing with writing my own parsers for them. I have a context free grammar parser already that works well. I am wondering if anyone can point me towards actually ...
3
votes
1answer
2k views

LR(1) - Items, Look Ahead

I am having diffuculties understanding the principle of lookahead in LR(1) - items. How do I compute the lookahead sets ? Say for an example that I have the following grammar: S -> AB A -> aAb | b ...
11
votes
3answers
21k views

How is this grammar LL(1)?

This is a question from the Dragon Book. This is the grammar: $S \to AaAb \mid BbBa $ $A \to \varepsilon$ $B \to \varepsilon$ The question asks how to show that it is LL(1) but not SLR(1). ...
3
votes
2answers
1k views

Recursive-Descent Predictive Parser for $S \rightarrow 0S1\ |\ 01$

I am having difficulty with one of the exercises in the Dragon Book: Exercise 2.4.1(c): Construct recursive-descent parsers, starting with the following grammars: $$S \rightarrow 0S1\ |\ 01$$...
3
votes
1answer
4k views

How to make a parse tree for the following propositional logic formula?

I have a formula $ \neg((q \implies \neg q) \vee p \vee (\neg q \implies (r \wedge p))) $. As it contains 3 subformulas between the $\vee$'s, how can i put it into a parse tree, as a parse tree ...
12
votes
2answers
5k views

Is there any way to distinguish between LL(k) and LR(k) grammar?

I am recently studying about Compilers designing. I came to know about two types of grammar one is LL grammar and other is LR grammar. We also know the facts that every LL grammar is LR that is LL ...
7
votes
1answer
12k views

Left-Factoring a grammar into LL(1)

I have a homework assignment where I need to convert a grammar into LL(1). I've already removed the left recursion, but I'm having trouble doing left-factoring. All of the examples I've found are ...
4
votes
2answers
21k views

Understanding LEADING and TRAILING operations of an operator precedence grammar

I want to understand what the LEADING and TRAILING of non-terminal in an operator precedence grammar physically mean. I am ...
1
vote
1answer
150 views

Phrase generators for use with testing grammars that don't use a seed

In helping someone understand phrase generators for use with testing grammars, think compiler test cases, I noted that I have never found a phrase generator that is knowledgeable of the grammar, and ...
1
vote
2answers
602 views

Can an LL(k) parser parse any grammar without left recursion or common prefixes?

I'm being asked to create a "top down grammar" for a certain language (I'm pretty sure there's no such thing as a "top down grammar" but I think it means write a grammar that an LL(k) parser can parse)...
14
votes
2answers
2k views

What is an IELR(1)-parser?

I try to teach myself the usage of bison. The manpage bison(1) says about bison: Generate a deterministic LR or generalized LR (GLR) parser employing LALR(1), IELR(1), or canonical LR(1) parser ...
4
votes
1answer
567 views

Is this phrase structure grammar from my textbook correct?

I just started reading "Parsing Techniques, A Practical Guide", Second Edition, by Dick Grune and Ceriel J.H. Jacobs. On page 12, the authors start describing a set of rules that can be used to ...
2
votes
3answers
2k views

Is this language LL(1) parseable?

I tried to find a simple example for a language that is not parseable with an LL(1) parser. I finally found this language. $$L=\{a^nb^m|n,m\in\mathbb N\land n\ge m\}$$ Is my hypothesis true or is ...
2
votes
1answer
1k views
7
votes
1answer
368 views

Can abstract syntax trees be unparsed in subexponential time?

Abstract problem description The way I see it, unparsing means to create a token stream from an AST, which when parsed again produces an equal AST, i.e. ...
1
vote
2answers
1k views

LL(1) parsing table of left-recursive grammar

I have been taking a compiler course of Stanford on coursera. I have a slight misunderstanding on the parsing table of the following grammar: S -> Sa | b According to the professor parsing table ...
1
vote
1answer
141 views

What's wrong with this LL grammar? (very short)

S --> Ta | b | Sc T --> Tc | λ This isn't an LL grammar but I need it to be so I can do a parse table. The problem is that no matter how much I try I never ...
2
votes
1answer
123 views

Given an LR grammar G and a string w, is it possible to quickly find all substrings in w that are in L(G)?

Say I have an LR grammar G and a string w. I know that I can check if w is in the language of G in linear time. But what if w itself is not in the language of G, but I want to find all substrings of w ...
6
votes
1answer
291 views

Determining whether a CFG is $LL(k)$ for any $k$?

In Knuth's original paper on $LR(k)$ grammars, he proved that the decision problem "Given a CFG $G$, is there a $k$ such that $G$ is an $LR(k)$ grammar?" is undecidable. Is there a similar result ...
14
votes
1answer
233 views

When did $LR(k)$ acquire the meaning “left-to-right scan, rightmost derivation?”

According to the Wikipedia article, the L in $LR(k)$ means "left-to-right scan", and the "R" means "rightmost derivation." However, in Knuth's original paper on $LR(k)$ grammars, he defines $LR(k)$ (...
8
votes
1answer
17k views

Left recursion and left factoring — which one goes first?

if I have a grammar having a production that contains both left recursion and left factoring like $\qquad \displaystyle F \to FBa \mid cDS \mid c$ which one has priority, left recursion or left ...
16
votes
2answers
4k views

Are regular expressions $LR(k)$?

If I have a Type 3 Grammar, it can be represented on a pushdown automaton (without doing any operation on the stack) so I can represent regular expressions by using context free languages. But can I ...
6
votes
2answers
173 views

Computing follow sets conservatively for a PEG grammar

Given a parsing expression grammar (PEG) grammar and the name of the start production, I would like to label each node with the set of characters that can follow it. I would be happy with a good ...
12
votes
2answers
2k views

Does the language of Regular Expressions need a push down automata to parse it?

I want to convert a user entered regular expression into an NFA so that I can then run the NFA against a string for matching purposes. What is the minimum machine that can be used to parse regular ...
0
votes
1answer
483 views

Is this grammar ambiguous?

I have the grammar: $\qquad \begin{align} S &\to S = P \mid S \neq P \mid P \\ P &\to NUM \end{align}$ This grammar suffers from left recursion. To eliminate left recursion, I got: $\...
7
votes
1answer
954 views

reduce reduce and shift reduce error in LALR grammar

I have to write a grammar for Pascal, and there is just one thing that is causing problems. Lets say we have operators (sorted by priority from low to high): Postfix ...
4
votes
1answer
445 views

From the LR(1) parsing table, can we deduce that it is also an LALR and SLR table?

There is this question I read somewhere but could not answer myself. Assume I have an LR(1) Parsing table. Is there any way that just by looking at it and its items, can I deduce that it is also a ...
13
votes
3answers
3k views

Why is using a lexer/parser on binary data so wrong?

I often work with lexer/parsers, as opposed to a parser combinator and see people who never took a class in parsing, ask about parsing binary data. Typically the data is not only binary but also ...
8
votes
3answers
4k views

Deriving the regular expression for C-style /**/ comments

I'm working on a parser for a C-style language, and for that parser I need the regular expression that matches C-style /**/ comments. Now, I've found this expression on the web: ...

1 4 5 6 7 8