Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.compilers > #195 > unrolled thread

Parsing C#-like generics

Back to article view | Back to comp.compilers

Contents

  Parsing C#-like generics "Harold Aptroot" <harold.aptroot@gmail.com> - 2011-07-11 20:22 +0200
    Re: Parsing C#-like generics Hans-Peter Diettrich <DrDiettrich1@aol.com> - 2011-07-12 13:25 +0100
      Re: Parsing C#-like generics BGB <cr88192@hotmail.com> - 2011-07-14 13:13 -0700
    Re: Parsing C#-like generics BGB <cr88192@hotmail.com> - 2011-07-12 16:39 -0700
    Re: Parsing C#-like generics "Ben L. Titzer" <ben.titzer@gmail.com> - 2011-07-13 10:19 -0700

#195 — Parsing C#-like generics

Hi,

I'm having some trouble parsing generics when mixed with comparisons. The
way I try to do it, there is an ambiguity between LessThan and a "list of
types between angle brackets".
For example, x<x>(x<x) should be syntactically OK, and it should be parsed
to a function call x with a type parameter list < x > and a single argument
which is the expression x<x (ok not really, I threw in semantics here to
make it clearer, the actual result should just be an AST).
My parser generator (GOLD parsing system) complains about a shift-reduce
error, and the parser it produces doesn't want to parse any expression with
a LessThan in it because it believes that to be a incomplete type list
(lacking a closing > )

I know it is actually inherently ambiguous, because t<t2>(t3) could mean two
things:
- LessThan(t, BiggerThan(t2, t3)
- invoke t<t2> with argument t3
In that case I want to pick option two.
For t<t2>t3 I want to pick option one, not report "missing ( "

Can this be done with an LALR parser at all? If so, how?

harold

[toc] | [next] | [standalone]

#197

Harold Aptroot schrieb:

> I'm having some trouble parsing generics when mixed with comparisons. The
> way I try to do it, there is an ambiguity between LessThan and a "list of
> types between angle brackets".
> For example, x<x>(x<x) should be syntactically OK, and it should be parsed
> to a function call x with a type parameter list < x > and a single argument
> which is the expression x<x (ok not really, I threw in semantics here to
> make it clearer, the actual result should just be an AST).

IMO you should better separate declarations from code (statements,
expressions). Then the parser will "know" from that context, that a
declaration can contain  <x> type lists, but not x<y expressions.

Above example should parse better as
   x<x>{x<x}
where the C style braces around statement blocks allow for better
disambiguation of the < token.

DoDi

[toc] | [prev] | [next] | [standalone]

#200

On 7/12/2011 5:25 AM, Hans-Peter Diettrich wrote:
> Harold Aptroot schrieb:

<snip>

> IMO you should better separate declarations from code (statements,
> expressions). Then the parser will "know" from that context, that a
> declaration can contain<x>  type lists, but not x<y expressions.
>
> Above example should parse better as
>     x<x>{x<x}
> where the C style braces around statement blocks allow for better
> disambiguation of the<  token.

the problem though is that often there are good reasons to allow these
types of things to appear in related contexts.

for example, if using a C-like declaration syntax, but without the aide
of having all types and declarations known up front, one will have to
deal with the potential ambiguity during parsing as to whether they are
dealing with one type of expression or another, and potentially need to
use some level of back-tracking to work this out.

part of this issue is because, in statement context, one of 3 different
major elements may appear:
a declaration;
a plain statement;
an expression.

given each may appear and it may not be possible to know up-front which
is present, one will have to tread carefully WRT avoiding ambiguities
between them, as an otherwise innocent seeming piece of syntax may lead
to potential misparsing elsewhere in the language. allowing too many
potential cases of misparses may frustrate programmers with otherwise
valid seeming code stepping on syntactic edge cases and being parsed as
something unintended.


better then IMO is to try to treat, declarations, statements, and
expressions, effectively as a unified whole (basically, a giant
expression tower which also includes statements and declarations as part
of its lower-end, essentially as precedence levels below the comma
operator). as well, one can try to avoid introducing syntactic
ambiguities wherever possible.


doing this may also allow in some cases allowing for much more compact
syntax, as extra typing can be left out which would otherwise be
required to disambiguate the syntax.

consider as a contrived example:
Foo foo(x)fun(x)new Foo(x);(x);

(nevermind that its meaning may not be entirely obvious, but code like
this may be written in my own language, which otherwise has a mostly
C-family style syntax.)


if the above were translated into a purer ActionScript style syntax, it
would look more like:
function foo(x):Foo { return(function(x){return(new Foo(x));}(x)); }

but, in my language, a few of these constructions can be left off (the
latter is valid syntax in my language as well, and is more-or-less
equivalent). all this is left as a matter of style.

side note: "foo(x)fun(x)new Foo(x);(x);", although only trivially
different, is not valid in my language, as now the parser has no idea
that it is looking at a function declaration.


however, as a tradeoff, I ended up having to omit C/Java style casts,
and ended up using a slightly nasty-looking syntax for attributes, each
because they created ambiguities with other parts of the syntax.

"x=(int)y;" is not valid, but would need to be written as "x=y as! int;"
("as" and "as!" are both casts, but differ as to how they handle cast
failures).

similarly, "$[foo]" or "$[foo(bar)]" is the syntax for attributes,
mostly because initially I was using C#-style "[foo(bar)]" attributes,
but these clashed in an annoying way with the current array syntax, and
the originally planned disambiguation rules would have been a little
nasty. unambiguous parsing would depend on subsequent syntax for
disambiguation, and I prefer to have it possible to know within a few
tokens which syntactic form is present, rather than potentially parsing
a large chunk of code only to discover that the wrong path had been
followed.

note that "@foo(bar)" probably would also have worked, but "$[...]" was
what I decided on.

as well as other "weird" syntax:
"[1,2,3]SB" for a 3-element signed byte array, mostly as I lacked any
good way to put it in prefix position ("#SB[1,2,3]" wouldn't have worked
for other reasons);
"[1,2,3]:sbyte" is equivalent to the above;
...

this is a major downside though:
the more features one tries to allow through a compact syntax, the more
hair that tends to appear, and it may risk leading to constructions that
are just plain nasty looking.


it is also made more difficult if one avoids depending on prior
declarations as context (frequently used for disambiguation in C and C++
syntax), which IMO has a number of drawbacks (creates dependency issues,
can slow down the parser, ...).

preferably also avoided is contextual semantic dependencies, where a
given expression may have very different semantics depending on the
context in which it is used. this can complicate the compiler and
potentially also confuse the user.


a more plain syntax, say, plain JavaScript style, one will not have so
many of these issues as pretty much everything in statement context is
either a plain expression, or uses a keyword to indicate what it is (the
'function' or 'var' keywords disambiguate these sorts of things). there
are merits to this route as well, as having most things indicated
explicitly via keywords makes the parser a good deal simpler.

ActionScript goes and adds a few things to the basic JavaScript style
syntax, notably the use of modifiers and explicit types, but most of
these are relatively straightforward (since the modifiers are themselves
keywords, and several other special cases are introduced mostly via the
introduction of additional keywords into certain contexts, ...).


or such...

[toc] | [prev] | [next] | [standalone]

#198

On 7/11/2011 11:22 AM, Harold Aptroot wrote:
> Hi,
>
> I'm having some trouble parsing generics when mixed with comparisons. The
> way I try to do it, there is an ambiguity between LessThan and a "list of
> types between angle brackets".

<snip>

>
> Can this be done with an LALR parser at all? If so, how?
>

don't know about LALR, but in general, the solution I would think would
be to require each '<' to have a matching '>' and exclude expressions
which contain comparisons.

say, we have the construction (informal BNF-like syntax here):
sharplist = '<' sharpargs '>'
sharpargs = sharparg [ ',' sharpargs]

generic = qname sharplist

generic could then be used wherever a generic is needed, possibly nearer
the top of the expression tower (higher precedence), or it could only be
placed in contexts where a type-name is expected (this depends some on
language, such as whether or not expressions and type-expressions are
unified, ...).


now, what about sharparg?

it is an expression type that presumably excludes comparrisons:
sharparg = expr_addsub		//+,- and above

this way, since we only have the top end of the precedence tower, the
'<' and '>' operators are excluded, and thus will not be eaten by the
expression parsing.


so, an expression like:
T<x,y>x

will parse as: T<x,y> followed by x.


should probably work I think, and wont (usually) give an unintended parsing.

except when someone types:
"foo(x<y, y>z);"

and wonders why they get a syntax error... ("parse error before 'z'.",
or similar).


next issue though is how to address things like:
T<V<x, y>>

where a naive tokenizer will parse '>>' as a single token rather than
'>' followed by '>'.

in my parsers, it is less of an issue since I use recursive descent and
tokenize inline, hence I can cheat it, but with a more generic lexer one
might have to, say, treat '>>' itself as a special case.

[toc] | [prev] | [next] | [standalone]

#199

On Jul 11, 11:22 am, "Harold Aptroot" <harold.aptr...@gmail.com>
> I'm having some trouble parsing generics when mixed with comparisons. The
> way I try to do it, there is an ambiguity between LessThan and a "list of
> types between angle brackets".
> For example, x<x>(x<x) should be syntactically OK, and it should be parsed
> to a function call x with a type parameter list < x > and a single argument
> which is the expression x<x (ok not really, I threw in semantics here to
> make it clearer, the actual result should just be an AST).
> My parser generator (GOLD parsing system) complains about a shift-reduce
> error, and the parser it produces doesn't want to parse any expression with
> a LessThan in it because it believes that to be a incomplete type list
> (lacking a closing > )
>
> I know it is actually inherently ambiguous, because t<t2>(t3) could mean
> two things:
> - LessThan(t, BiggerThan(t2, t3)
> - invoke t<t2> with argument t3
> In that case I want to pick option two.
> For t<t2>t3 I want to pick option one, not report "missing ( "
>
> Can this be done with an LALR parser at all? If so, how?


One trick I've used in the past is to lex the '<' that introduces a
type parameter list as part of the identifier:

"foo" would lex as a single IDENT token.
and
"foo<" would lex as a single PARAMETERIZED_IDENT token.
and
"foo <" would lex as IDENT followed by LESS_THAN

You can then use the IDENT and PARAMETERIZED_IDENT tokens in various
places in the grammar, with PARAMETERIZED_IDENT being followed by a
type list and a '>' token.

This then requires any use of the '<' operator that follow an
identifer to have intervening whitespace. It also requires that any
parameterization of an identifier not have intervening whitespace. I
think it's a decent tradeoff if you are defining the language
yourself, but won't work for languages with more complex rules for
resolving the ambiguity.

[toc] | [prev] | [standalone]

Back to top | Article view | comp.compilers

csiph-web