2 replaced http://linguistics.stackexchange.com/ with https://linguistics.stackexchange.com/
source | link

There are many general context-free parser that can parse ambiguous sentences (according to an ambiguous grammar). They come under various names, notably dynamic-programming or chart parsers. The best known one, and next to simplest, is probably the CYK parser that you have been using. That generality is needed since you have to handle multiple parses and may not know till the end whether you are dealing with an ambiguity or not.

From what you say, I would think that CYK is not such a bad choice. You probably do not have much to gain by adding predictiveness (LL or LR), and it may actually have a cost by discriminating computations that should be merged rather than discriminated (especially in the LR case). They may also have a corresponding cost in the size of the parse forest that is produced (which may have a role in ambiguity errors). Actually, while I am not sure how to compare formally the adequacy of the more sophisticated algorithms, I do know that CYK does give good computation sharing.

Now, I do not believe there is much literature on general CF parsers for ambiguous grammars that should only accept unambiguous input. I do not recall seeing any, probably because even for technical documents, or even programming languages, syntactic ambiguity is acceptable as long as it can be resolved by other means (e.g. ambiguity in ADA expressions).

I am actually wondering why you want to change your algorithm, rather than stick to what you have. That might help me understand what kind of change could best help you. Is it a speed issue, is it the representation of parses, or is it the error detection and recovery?

The best way to represent multiple parses is with a shared forest, which is simply a context-free grammar that generates only your input, but with exactly all the same parse trees as the DSL grammar. That makes it very easy to understand and process. For more details, I suggest you look at this answerthis answer I gave on the linguistic site. I do understand that you are not interested in getting a parse forest, but a proper representation of parse forest can help you give better messages as to what the ambiguity problen is. It could also help you decide that the ambiguity does not matter in some cases (associativity) if you wantd to do that.

You mention the processing time constraints of your DSL grammar, but give no hint as to its size (which does not means that I could answer with figures it you did).

Some error processing can be integrated in these general CF algorithms in simple ways. But I would need to understand what kind of error processing you expect to be more affirmative. Would you have some examples.

I am a bit ill at ease to say more, because I do not understand what are really your motivations and constraints. On the basis of what you say, I would stick to CYK (and I do know the other algorithms and some of their properties).

There are many general context-free parser that can parse ambiguous sentences (according to an ambiguous grammar). They come under various names, notably dynamic-programming or chart parsers. The best known one, and next to simplest, is probably the CYK parser that you have been using. That generality is needed since you have to handle multiple parses and may not know till the end whether you are dealing with an ambiguity or not.

From what you say, I would think that CYK is not such a bad choice. You probably do not have much to gain by adding predictiveness (LL or LR), and it may actually have a cost by discriminating computations that should be merged rather than discriminated (especially in the LR case). They may also have a corresponding cost in the size of the parse forest that is produced (which may have a role in ambiguity errors). Actually, while I am not sure how to compare formally the adequacy of the more sophisticated algorithms, I do know that CYK does give good computation sharing.

Now, I do not believe there is much literature on general CF parsers for ambiguous grammars that should only accept unambiguous input. I do not recall seeing any, probably because even for technical documents, or even programming languages, syntactic ambiguity is acceptable as long as it can be resolved by other means (e.g. ambiguity in ADA expressions).

I am actually wondering why you want to change your algorithm, rather than stick to what you have. That might help me understand what kind of change could best help you. Is it a speed issue, is it the representation of parses, or is it the error detection and recovery?

The best way to represent multiple parses is with a shared forest, which is simply a context-free grammar that generates only your input, but with exactly all the same parse trees as the DSL grammar. That makes it very easy to understand and process. For more details, I suggest you look at this answer I gave on the linguistic site. I do understand that you are not interested in getting a parse forest, but a proper representation of parse forest can help you give better messages as to what the ambiguity problen is. It could also help you decide that the ambiguity does not matter in some cases (associativity) if you wantd to do that.

You mention the processing time constraints of your DSL grammar, but give no hint as to its size (which does not means that I could answer with figures it you did).

Some error processing can be integrated in these general CF algorithms in simple ways. But I would need to understand what kind of error processing you expect to be more affirmative. Would you have some examples.

I am a bit ill at ease to say more, because I do not understand what are really your motivations and constraints. On the basis of what you say, I would stick to CYK (and I do know the other algorithms and some of their properties).

There are many general context-free parser that can parse ambiguous sentences (according to an ambiguous grammar). They come under various names, notably dynamic-programming or chart parsers. The best known one, and next to simplest, is probably the CYK parser that you have been using. That generality is needed since you have to handle multiple parses and may not know till the end whether you are dealing with an ambiguity or not.

From what you say, I would think that CYK is not such a bad choice. You probably do not have much to gain by adding predictiveness (LL or LR), and it may actually have a cost by discriminating computations that should be merged rather than discriminated (especially in the LR case). They may also have a corresponding cost in the size of the parse forest that is produced (which may have a role in ambiguity errors). Actually, while I am not sure how to compare formally the adequacy of the more sophisticated algorithms, I do know that CYK does give good computation sharing.

Now, I do not believe there is much literature on general CF parsers for ambiguous grammars that should only accept unambiguous input. I do not recall seeing any, probably because even for technical documents, or even programming languages, syntactic ambiguity is acceptable as long as it can be resolved by other means (e.g. ambiguity in ADA expressions).

I am actually wondering why you want to change your algorithm, rather than stick to what you have. That might help me understand what kind of change could best help you. Is it a speed issue, is it the representation of parses, or is it the error detection and recovery?

The best way to represent multiple parses is with a shared forest, which is simply a context-free grammar that generates only your input, but with exactly all the same parse trees as the DSL grammar. That makes it very easy to understand and process. For more details, I suggest you look at this answer I gave on the linguistic site. I do understand that you are not interested in getting a parse forest, but a proper representation of parse forest can help you give better messages as to what the ambiguity problen is. It could also help you decide that the ambiguity does not matter in some cases (associativity) if you wantd to do that.

You mention the processing time constraints of your DSL grammar, but give no hint as to its size (which does not means that I could answer with figures it you did).

Some error processing can be integrated in these general CF algorithms in simple ways. But I would need to understand what kind of error processing you expect to be more affirmative. Would you have some examples.

I am a bit ill at ease to say more, because I do not understand what are really your motivations and constraints. On the basis of what you say, I would stick to CYK (and I do know the other algorithms and some of their properties).

1
source | link

There are many general context-free parser that can parse ambiguous sentences (according to an ambiguous grammar). They come under various names, notably dynamic-programming or chart parsers. The best known one, and next to simplest, is probably the CYK parser that you have been using. That generality is needed since you have to handle multiple parses and may not know till the end whether you are dealing with an ambiguity or not.

From what you say, I would think that CYK is not such a bad choice. You probably do not have much to gain by adding predictiveness (LL or LR), and it may actually have a cost by discriminating computations that should be merged rather than discriminated (especially in the LR case). They may also have a corresponding cost in the size of the parse forest that is produced (which may have a role in ambiguity errors). Actually, while I am not sure how to compare formally the adequacy of the more sophisticated algorithms, I do know that CYK does give good computation sharing.

Now, I do not believe there is much literature on general CF parsers for ambiguous grammars that should only accept unambiguous input. I do not recall seeing any, probably because even for technical documents, or even programming languages, syntactic ambiguity is acceptable as long as it can be resolved by other means (e.g. ambiguity in ADA expressions).

I am actually wondering why you want to change your algorithm, rather than stick to what you have. That might help me understand what kind of change could best help you. Is it a speed issue, is it the representation of parses, or is it the error detection and recovery?

The best way to represent multiple parses is with a shared forest, which is simply a context-free grammar that generates only your input, but with exactly all the same parse trees as the DSL grammar. That makes it very easy to understand and process. For more details, I suggest you look at this answer I gave on the linguistic site. I do understand that you are not interested in getting a parse forest, but a proper representation of parse forest can help you give better messages as to what the ambiguity problen is. It could also help you decide that the ambiguity does not matter in some cases (associativity) if you wantd to do that.

You mention the processing time constraints of your DSL grammar, but give no hint as to its size (which does not means that I could answer with figures it you did).

Some error processing can be integrated in these general CF algorithms in simple ways. But I would need to understand what kind of error processing you expect to be more affirmative. Would you have some examples.

I am a bit ill at ease to say more, because I do not understand what are really your motivations and constraints. On the basis of what you say, I would stick to CYK (and I do know the other algorithms and some of their properties).