indentation-sensitive parsing for parsec：压痕敏感分析秒差距.pdf

Indentation-Sensitive Parsing for Parsec Michael D. Adams University of Illinois at Urbana/Champaign / ?mer S. A ?gacan TOBB University of Economics and Technology / Abstract Several popular languages including Haskell and Python use the indentation and layout of code as an essential part of their syntax. In the past, implementations of these languages usedad hoctech- niques to implement layout. Recent work has shown that a simple extension to context-free grammars can replace thesead hoctech- niques and provide both formal foundations and ef?cient parsing algorithms for indentation sensitivity. However, that previous work is limited to bottom-up, LR(k) parsing, and binator-based parsing frameworks including Parsec use top-down algorithms that are outside its scope. This paper remedies this by showing how to add indentation sensitivity to parsing frameworks like Parsec. It explores both the formal semantics of and ef?cient algorithms for indentation sensitivity. It derives a Parsec-based library for indentation-sensitive parsing and presents benchmarks on a real-world language that show its ef?ciency and practicality. Categories and Subject Descriptors [Programming Lan- guages]: Formal De?nitions and Theory—Syntax; [Pro- gramming Languages]: Processors—Parsing; [Mathemati- cal Logic and Formal Languages]: Grammars and Other Rewriting Systems—Parsing General TermsAlgorithms, Languages KeywordsParsing; Parsec; Indentation sensitivity; Layout; Off- side rule 1. Introduction Languages such as Haskell (Marlow (ed.) 2010) and Python (Python) use the indentation of code to delimit various grammati- cal forms. For example, in Haskell, the contents of alet,where, do, orcaseexpression can be indented relative to the surround- ing code instead of being explicitly delimited by curly braces. For example, one may write: umR f = loop where loop acc (x:xs) = (acc’’, x’: xs’) where (acc’’, x’) = f acc’ x (acc’, xs’) = loop acc xs loop acc [] = (acc, []) Copyright