Bison Question: Ambiguous Grammar?
Hi, I have a question about Bisons GLR parser. Is there a way for Bison (in %glr-parser mode) to return a parse tree (doesn't matter which) when parsing according to an ambiguous grammar? Thanks in advance, /Claus. -- Claus Brabrand, Ph.D. [EMAIL PROTECTED] http://www.daimi.au.dk/~brabrand/ ___ Help-bison@gnu.org http://lists.gnu.org/mailman/listinfo/help-bison
Virus detected
GROUP securiQ.Watchdog Server: MHUB107 --- The following attachments contained viruses and were removed in order to protect Ernst & Young system resources. Please innoculate the infected files and resend them. --- Mail-Info From: help-bison@gnu.org To:[EMAIL PROTECTED] Rec.: [EMAIL PROTECTED] [EMAIL PROTECTED] Date: 05/06/2005 07:46:32 AM Subject: Re: --- file contains virus:our_secret.zip ___ Help-bison@gnu.org http://lists.gnu.org/mailman/listinfo/help-bison
Re: Bison Question: Ambiguous Grammar?
At 12:49 +0200 2005/05/06, Claus Brabrand wrote: I have a question about Bisons GLR parser. Is there a way for Bison (in %glr-parser mode) to return a parse tree (doesn't matter which) when parsing according to an ambiguous grammar? Bison never returns a parse tree. If you want that, you need to define its construction in the actions. When people ask that question, they often need much less; if you so want, you may precise your programming situation. -- Hans Aberg ___ Help-bison@gnu.org http://lists.gnu.org/mailman/listinfo/help-bison
Re: Bison Question: Ambiguous Grammar?
Hans Aberg wrote: At 12:49 +0200 2005/05/06, Claus Brabrand wrote: I have a question about Bisons GLR parser. Is there a way for Bison (in %glr-parser mode) to return a parse tree (doesn't matter which) when parsing according to an ambiguous grammar? Bison never returns a parse tree. If you want that, you need to define its construction in the actions. When people ask that question, they often need much less; if you so want, you may precise your programming situation. Hans, Thanks for your reply. Yes, I realize there's no parse tree beyond what I may chose to construct in the action code myself. What I meant is: is there a way for Bison to take the actions according to one (any) of the parses? I am using Bison in GLR-mode for code-generating syntax-directed transformations (executed in the action code). The grammars are highly ambiguous which is fine: I just want to execute actions for one (any) of the parses. I have a grammar which is capable of parsing a string (and returning a transformed string which is just the result of executing the corresponding action code). Now, when I add a certain production to this grammar, I get a parse error in the middle of the string it was able to parse without this extra production(?!?) What I don't understand is how adding a production to a grammar G can cause it to reject the string - it should just enlarge the language induced by the grammar - and so, that if it was capable of parsing my string before, it should also be able to do so after (with the extra production). This really puzzles me(?) Is Bison's GLR algorithm intended for ambiguous grammars or will it only work on the subset of grammars that are unambiguous (LALR(1) or not)? Maybe this particular production renders the grammar ambiguous (at least wrt. my input string - i.e. that my string has two parses). I would greatly appreciate any insights you might have! Thanks, /Claus. -- Claus Brabrand, Ph.D. [EMAIL PROTECTED] http://www.daimi.au.dk/~brabrand/ ___ Help-bison@gnu.org http://lists.gnu.org/mailman/listinfo/help-bison
Re: Bison Question: Ambiguous Grammar?
At 19:21 +0200 2005/05/06, Claus Brabrand wrote: Yes, I realize there's no parse tree beyond what I may chose to construct in the action code myself. What I meant is: is there a way for Bison to take the actions according to one (any) of the parses? The current Bison GLR parsers work so that when parsing an ambiguous rule, the parser splits, and parses without executing any actions until the ambiguous rule has finished parsing. Then the actions of the successful parses, if any, are executed. There is currently no way to get actions executed immediately, even though Paul Hilfinger, who wrote %glr, is considering this as a feature. I am using Bison in GLR-mode for code-generating syntax-directed transformations (executed in the action code). The grammars are highly ambiguous which is fine: I just want to execute actions for one (any) of the parses. Then you have to choose one of the parses according to the methods indicated in the Bison manual. I do not know if there is a way to avoid actions to be executed in the unwanted parses, if there is more than one successful parses; possibly you have to write the actions, so that they are not harmful in such a case. I have a grammar which is capable of parsing a string (and returning a transformed string which is just the result of executing the corresponding action code). Now, when I add a certain production to this grammar, I get a parse error in the middle of the string it was able to parse without this extra production(?!?) What I don't understand is how adding a production to a grammar G can cause it to reject the string - it should just enlarge the language induced by the grammar - and so, that if it was capable of parsing my string before, it should also be able to do so after (with the extra production). This really puzzles me(?) If the parser constructed all parse trees, that would be the case, but in LALR(1), and scans the rules in order. So then funny things can happen. I do not know if this is the case; you give no details. Also, you might ask this question in the newsgroup comp.compiles, providing the details. Is Bison's GLR algorithm intended for ambiguous grammars or will it only work on the subset of grammars that are unambiguous (LALR(1) or not)? Maybe this particular production renders the grammar ambiguous (at least wrt. my input string - i.e. that my string has two parses). When making this GLR extension, it should work with all ambiguous grammars. The drawback, though, is that it only splits the ambiguous rules, and then merges them when finished. Of one then wants to keep track of all parses, then one will have to do that via the actions. Thus, there is a difference between GLR based on LALR(1) or on LR(1). The advantage of this approach, though, over a genuinely non-deterministic parsing, is that the latter is very slow. -- Hans Aberg ___ Help-bison@gnu.org http://lists.gnu.org/mailman/listinfo/help-bison
