4 ms·

Are there any context & precedence sensitive parser algorithms? I've noticed most parsers are context free, yet most languages are context sensitive, so when t

Are there any context & precedence sensitive parser algorithms? I've noticed most parsers are context free, yet most languages are context sensitive, so when trying to parse such a language using a context free grammar, you end up having to do lots of tricks to try to work around the context sensitive things in the language. Feels odd almost all modern compilers decided to go for the hand-written approach, with a parser source code file that is usually in the range of 5000-20000 lines of code. There ought to be a simpler way to both define the grammar formally and to use that formal definition to actually parse the text.

jjtheblunt 9y ago
not sure you know of yacc and lex (see unix manpages for them, and likely oreilly books). they've been useful for literally decades.
jules 9y ago
Whether a language is context free depends on how much checking you want to happen in the parsing stage. A variable usage is valid only if that variable is in scope, and this trivially makes almost all languages context sensitive. Almost all programming languages become context free if you delay the checking of such errors to a subsequent stage instead of requiring it to be handled in the grammar. For example the following is syntactically valid Javascript according to the Javascript grammar, because the grammar does not handle variable scope: var foo = 0; var bar = boo; // typo Context free grammars are actually an overpowered formalism for programming languages except for variable scope. Most languages don't require more than LR(1). Monadic parser combinators can easily handle context sensitive grammars. The simplest example is a length prefixed field in network protocols. Context free grammars cannot parse this, but a monadic parser can read the length and then parse that many repetitions.
mhh__ 9y ago
Manually written parsers allow the programmers to have better control over error handling, error messages, and the overall architecture of the parser. Parser generators exist, and are used all over the place, but they aren't without their flaws.
hyperpallium 9y ago
yacc allows you to specify operator precedence declaratively (but not otherwise context sensitive). IIRC it's uses a shift-reduce algorithm. For a small yet real, working and useful example of parsing with yacc, have a look at jq (json query). In practice, a common long-term pattern for project is to start with yacc (because it's close to what you want: defining the grammar, then automatically parsing with it), but then switch to a hand-written recursive descent grammar later, primarily for more informative error messages (trying to do that in yacc quickly becomes unbelievably intricate and complex, requiring changes in the grammar definition to expose where the error needs to be detected, in part because yacc doesn't parse a grammar the way a user thinks about it. I think this is intrinsic to your ideal of automatically parsing with the definition, because error reporting has a different structure). A special-purpose custom parser can also be optimized for better time amd space performance. Much of those 20,000-30,000 LoC are for error reporting and efficiency. Recursive descent parsers are related to the formalism, and there are standard theoretical transformations to put them into a working form (e.g. removing left-recursion)... but I have to admit, it's all pretty hacky and ad hoc, just specifying the way, not the why, and so not the elegant automatic translation you'd like. I wpuld recommend you study parsers, an online course, or maybe read the excellent intro chapter of the second ed of the Aho et al Compilers book (aka the "dragon" book) which actually builds a simple compiler, but your ideals will only be disappointed. tl;dr you're right, but...

jjtheblunt 9y ago

not sure you know of yacc and lex (see unix manpages for them, and likely oreilly books). they've been useful for literally decades.

jules 9y ago

Whether a language is context free depends on how much checking you want to happen in the parsing stage. A variable usage is valid only if that variable is in scope, and this trivially makes almost all languages context sensitive. Almost all programming languages become context free if you delay the checking of such errors to a subsequent stage instead of requiring it to be handled in the grammar. For example the following is syntactically valid Javascript according to the Javascript grammar, because the grammar does not handle variable scope: var foo = 0; var bar = boo; // typo Context free grammars are actually an overpowered formalism for programming languages except for variable scope. Most languages don't require more than LR(1). Monadic parser combinators can easily handle context sensitive grammars. The simplest example is a length prefixed field in network protocols. Context free grammars cannot parse this, but a monadic parser can read the length and then parse that many repetitions.

mhh__ 9y ago

Manually written parsers allow the programmers to have better control over error handling, error messages, and the overall architecture of the parser. Parser generators exist, and are used all over the place, but they aren't without their flaws.

hyperpallium 9y ago

yacc allows you to specify operator precedence declaratively (but not otherwise context sensitive). IIRC it's uses a shift-reduce algorithm. For a small yet real, working and useful example of parsing with yacc, have a look at jq (json query). In practice, a common long-term pattern for project is to start with yacc (because it's close to what you want: defining the grammar, then automatically parsing with it), but then switch to a hand-written recursive descent grammar later, primarily for more informative error messages (trying to do that in yacc quickly becomes unbelievably intricate and complex, requiring changes in the grammar definition to expose where the error needs to be detected, in part because yacc doesn't parse a grammar the way a user thinks about it. I think this is intrinsic to your ideal of automatically parsing with the definition, because error reporting has a different structure). A special-purpose custom parser can also be optimized for better time amd space performance. Much of those 20,000-30,000 LoC are for error reporting and efficiency. Recursive descent parsers are related to the formalism, and there are standard theoretical transformations to put them into a working form (e.g. removing left-recursion)... but I have to admit, it's all pretty hacky and ad hoc, just specifying the way, not the why, and so not the elegant automatic translation you'd like. I wpuld recommend you study parsers, an online course, or maybe read the excellent intro chapter of the second ed of the Aho et al Compilers book (aka the "dragon" book) which actually builds a simple compiler, but your ideals will only be disappointed. tl;dr you're right, but...