Dyck context-free grammar formal definition?

Dyck context-free grammar formal definition?

Post by Georgios P » Mon, 27 Oct 2003 07:43:10


I am searching information about the
"Dyck context free grammar". From
a small search I have done, it seems that
this grammar is a kind of balanced parenthesis
grammar, but I am not completelly sure.
Does anybody knows of any sitations explaing
"Dyck grammars" or a formal definition?

Also, how easy is to generate sentences from
its language?

Thanks in advance,

George
 
 
 

1. Regular Tree Grammar vs. Context-Free Grammar

2. Parsing fully context-free grammars

Hi All,

A few months ago I completed a generator for recursive-decent parsers
from ABNF-defined grammars (APG - an ABNF Parser Generator). It was
done in an ad hoc way with no concern at all for reinventing the
wheel. I'm now backtracking a little and trying to find out which
wheel it is that I might have reinvented. The only other fully
context-free algorithms that I've been able to find so far are the
CYK, Earley and GLR algorithms. Are there any recursive-decent or
otherwise algorithms for fully context-free grammars that I should
know about?

Also, APG always disambiguates to a single parse tree. However,
looking at the "dangling else", I've found that is easy to get either
translation from the single parse tree. That is,

if(expr) then {if(expr) then {stmt} else {stmt}}
or
if(expr) then {if(expr) then {stmt}} else {stmt}.

It seems to me that this could be generalized to say, in effect, that
any tree from the forest can be emulated by any other. Does anyone
know of a contradiction to this?

A more complete examination of this problem and others with working
examples is available from my web site (www.coasttocoastresearch.com)

Comments and discussion would be welcome.

Lowell Thomas

3. Is it really Ok to assert that the Ada syntax is a context-free grammar ?

4. Regular & context-free grammar problem

5. Context-free grammar

6. Is it possible to generate a context-free grammar for a programming language?

7. O(n) Parsing For General Context-Free Grammars & Transductions

8. Make the C++ grammar context-free

9. Is it really Ok to assert that the Ada syntax is a context-free grammar ?

10. context-free grammars (cfg) for the language

11. Extended context-free grammar

12. Regular & context-free grammar problem

13. how to construct the context-free grammar for Rome digit?

14. Formal grammar & syntax of formal languages

15. Context-Free Expressions and Turing Expressions (was: Context Free Language)