# Questions tagged [parsing]

Parsing is the process of analyzing a string of symbols, either in natural language, computer languages or data structures, conforming to the rules of a formal grammar.

27 questions
Filter by
Sorted by
Tagged with
1answer
28 views

### Parsing a nested inference rule syntax

Consider this expression. $$\dfrac{\dfrac{\dfrac{\dfrac{}{\textsf{zero nat}}}{\textsf{succ(zero) nat}}}{\textsf{succ(succ(zero)) nat}}}{\textsf{succ(succ(succ(zero))) nat}}$$ I see several ...
0answers
17 views

### How to evaluate this type of arithmetic syntax tree in general?

I have a syntax tree, like this: Tree I can evaluate any syntax tree easily when there are no terms, with a similar code (I wrote a simpler pseudo code): ...
1answer
62 views

### An explicit algorithm to test whether a string of symbols is or is not well-formed in this language.

Consider the set of five symbols, $\{ (, ), p, ', *\}$. A variable is defined as $p$ followed by zero or more $'$s. A wff is inductively defined as follows: $1$. Every variable is a wff. $2$. If $x$ ...
1answer
27 views

### Unique parsing means?

After searching this site for the key words "unique parsing" "parsing" and "unique parsing lemma," and finding nothing really applicable to me (or as far as I could tell),...
1answer
31 views

### Is every sentential form also a right-sentential form?

Ullman's Introduction to Automata, Languages and Computing (1979) says 10.6 LR(0) GRAMMARS ... A right-sentential form is a sentential form that can be derived by a rightmost derivation. Is every ...
0answers
12 views

### How to characterize the set of grammars which recursive descent parsers can apply to?

How would you characterize the set of grammars which recursive descent parsers can apply to: no left recursion (both immediate and not) left factored no cycle no epsilon rule ... Predicative ...
0answers
20 views

### Are there subset/superset relations between the languages which can be parsed by these different kinds of parsers?

I have been confused by the different types of parsers listed in https://en.wikipedia.org/wiki/Parsing#Types_of_parsers and https://en.wikipedia.org/wiki/Template:Parsers Are there some top-down and ...
0answers
30 views

### Is a CFL parser counted as an automaton, and even a PDA?

Is a CFL parser counted as an automaton? Even more, is a CFL parser counted as a PDA? I found that a CFL parser is defined directly based on a CFG, while the concepts of CFG and PDA are defined ...
1answer
26 views

### Correctness properties, judgments and rules [closed]

Definition: sD means $s$ is a digit, i.e. $s$ is one of $0,1,\dots,9$. k Nat means $k\in\bf N$. Proposition: If sD <-> k Nat then sD and k Nat. I don't really understand what I have to prove. ...
1answer
19 views

### Proving a Formal Grammar Parses a String.

In summary, I am interested to know (at a high level) what a proof would look like, and what I would need to do in developing a grammar, to "prove" that the grammar matches some patterns I have in ...
0answers
114 views

### Can first-order logic be recognized by a pushdown automaton?

I have the belief that first-order logic cannot be recognized by a pushdown automaton because the automaton will have no way to keep track of the variables that are currently in scope. More precisely, ...
1answer
1k views

### Is First Order Logic Syntax Context Free?

If I were to build a first order logic parser could I do it using a context free parser generator (like bison)? I found some articles where First Order Logic Syntax is described with EBNF notation, ...
1answer
47 views

### This is a ll(1) of logic propositions?

I have this is grammar : F = F and F F = F or F F = F => F F = F <=> F F = not F F = (F) D = a but this grammar has a ambiguity , i'm Stripped a ...
2answers
83 views

### Interpreting “pairwise”

I have the following exercise. Can four lines in space (not necessarily passing through the same point) be pairwise perpendicular? Does it mean (given 4 lines $a$, $b$, $c$, and $d$): $a\perp b$; ...
1answer
117 views

### I am confused about how epsilon works in parsing tables (or my book is wrong)?

So I'm reading my lecture notes and something really confuses me: Shouldn't the [Y,+] entry produce an error as there is no possible way you can get the string '+' from Y? Why then does it say it ...
1answer
555 views

### Evaluating an arithmetic abstract syntax tree [closed]

This might be very simplistic for this forum (apologies, if so). How does one evaluate the tree below. I am not looking for a solution, just assistance in how to evaluate it: I assume I start at the ...
1answer
251 views

### Which of the following string have two or more parse trees?

Consider the following ambiguous grammar: $S→A|BC$ $A→aAC|B$ $C→bCc|c$ $B→aBb|\in$ Which of the following string have two or more parse trees? $aaabbbbbcc$ $aaabb$ $aabb$ None of these My ...
1answer
76 views

### Create a formula for order of parenthesis

I am stumped at creating a formula (for a coded math problem evaluator) that finds what is within the parenthesis. It gets tricky when you have () within ...
1answer
126 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 ...
0answers
20 views

### Relationships between $\operatorname{LL}(k)$, $\operatorname{LR}(k)$ language sets

I'm trying to establish (through constructing a Hasse diagram) the subset relationship between the classes of languages that can be parsed by $\operatorname{LL}(k)$ and $\operatorname{LR}(k)$ parsers. ...
0answers
64 views

1answer
2k views

### Eliminating Epsilon Production for Left Recursion Elimination

Im following the algorithm for left recursion elimination from a grammar.It says remove the epsilon production if there is any I have the following grammer ...
1answer
4k views

### How to prove CYK algorithm has $O(n^3)$ running time

I have a final coming up in few days, and the professor mentioned the CYK algorithm. I want to be prepared for the final. I'm trying to find out how to prove the algorithm has worst case running time ...