# 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.

23 questions
Filter by
Sorted by
Tagged with
19 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 ...
11 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 ...
16 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 ...
26 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 ...
25 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. ...
17 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 ...
108 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, ...
796 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, ...
46 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 ...
57 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$; ...
113 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 ...
500 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 ...
101 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 ...
74 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 ...
81 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 ...
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. ...
64 views