Is C#’s lambda expression grammar LALR(1)?

by

First off, parser theory was always one of my weak points. I mostly work on semantic analyzers.

Second, all the C# parsers I’ve ever worked on have been hand-generated recursive descent parsers. One of my former colleagues who does have a strong background in parser theory did build his own parser generator and fed the C# grammar into it successfully, but I do not know what sort of egregious hacks doing so entailed.

So what I’m saying here is to take this answer with the appropriate amount of skepticism.

As you note, lambdas are slightly vexing because you’ve got to be careful about that parenthesized expression — it might be a parenthesized expression, a cast operator or a lambda parameter list, and the lambda parameter list could be in several different forms. But all things considered, adding lambdas to C# 3.0 was relatively easy, grammatically; hacking up the parser was not too difficult — it was the semantic analysis that was a bear for lambdas.

The real vexing problems in the C# grammar as far as look-ahead goes are generics and casts.

Generics were added in C# 2, after the language already had >>, > and < operators, all of which can cause weird problems when you throw generics into the mix.

The classic problem is of course A ( B < C, D > ( E ) ) Does the invocation of method A take two arguments: B < C and D > (E) or one, B<C,D>( E )?

The rule to disambiguate is:

If a sequence of tokens can be parsed as a simple-name, member-access, or pointer-member-access ending with a type-argument-list, the token immediately following the closing > token is examined. If it is one of ( ) ] : ; , . ? == != then the type-argument-list is retained as part of the simple-name, member-access or pointer-member-access and any other possible parse of the sequence of tokens is discarded. Otherwise, the type-argument-list is not considered part of the simple-name, member-access or pointer-member-access, even if there is no other possible parse of the sequence of tokens.

The second problem with the grammar goes back to C# 1.0, and that’s the cast operator. The problem is that (x)-y could mean “cast -y to type x” or it could mean to subtract y from x. The rule here is:

A sequence of one or more tokens enclosed in parentheses is considered the start of a cast-expression only if at least one of the following are true:

The sequence of tokens is correct grammar for a type, but not for an expression.

The sequence of tokens is correct grammar for a type, and the token immediately following the closing parentheses is the token “~”, the token “!”, the token “(“, an identifier, a literal, or any keyword except as and is.

The rules that disambiguate both cases involve potentially large look-aheads in theory, but in practice you very rarely have to back up the parser very far.

More Related Contents:

  1. Identify if a string is a number
  2. Parse DateTime with time zone of form PST/CEST/UTC/etc
  3. Get URL parameters from a string in .NET
  4. JavaScriptSerializer.Deserialize – how to change field names
  5. Read and parse a Json File in C#
  6. Parsing FtpWebRequest ListDirectoryDetails line
  7. Why can’t DateTime.Parse parse UTC date
  8. Pulling data from a webpage, parsing it for specific pieces, and displaying it
  9. How to parse very huge XML Files in C#? [duplicate]
  10. Why does TimeSpan.ParseExact not work
  11. Using ANTLR 3.3?
  12. How to write a Parser in C#? [closed]
  13. Double.TryParse or Convert.ToDouble – which is faster and safer?
  14. Casting vs Converting an object toString, when object really is a string
  15. Best way to parse float?
  16. How to create a new language for use in Visual Studio
  17. Read a XML (from a string) and get some fields – Problems reading XML
  18. Lex/Yacc for C#?
  19. Improving/Fixing a Regex for C style block comments
  20. How can I use HTML Agility Pack to retrieve all the images from a website?
  21. How to fix ill-formed HTML with HTML Agility Pack?
  22. c# convert string expression to a boolean expression [closed]
  23. Parsing Performance (If, TryParse, Try-Catch)
  24. What is the C# equivalent of NaN or IsNumeric?
  25. reading two integers in one line using C#
  26. Httplistener and file upload
  27. How to get all input elements in a form with HtmlAgilityPack without getting a null reference error
  28. Where is a good Address Parser [closed]
  29. Are there .NET Framework methods to parse an email (MIME)?
  30. regex match keywords that are not in quotes

Leave a Comment