检索结果-内蒙古大学图书馆

parser combinators for Context-Free Path Querying 9

Parser Combinators for Context-Free Path Querying

9th ACM SIGPLAN International Symposium on Scala (Scala) as part of the ACM SIGPLAN International Conference on Functional Programming (ICFP)

作者： Verbitskaia, Ekaterina Kirillov, Ilya Nozkin, Ilya Grigorev, Semyon St Petersburg State Univ St Petersburg Russia

ISBN: (纸本)9781450358361

Transparent integration of a domain-specific language for specification of context-free path queries (CFPQs) into a general-purpose programming language as well as static checking of errors in queries may greatly simplify the development of applications using CFPQs. LINQ and ORM can be used for the integration, but they have issues with flexibility: query decomposition and reusing of subqueries are a challenge. Adaptation of parser combinators technique for paths querying may solve these problems. Conventional parser combinators process linear input, and only the Trails library is known to apply this technique for path querying. Trails suffers the common parser combinators issue: it does not support left-recursive grammars and also experiences problems in cycles handling. We demonstrate that it is possible to create general parser combinators for CFPQ which support arbitrary context-free grammars and arbitrary input graphs. We implement a library of such parser combinators and show that it is applicable for realistic tasks.

关键词： Graph Databases Language-Constrained Path Problem Context-Free Path Querying Context-Free Language Reachability parser combinators Generalized LL GLL Neo4j Scala

来源：评论

学校读者我要写书评

暂无评论

parser combinators for ambiguous left-recursive grammars

Parser combinators for ambiguous left-recursive grammars

引用

10th International Symposium on Practical Aspects of Declarative Languages

作者： Frost, Richard A. Hafiz, Rahmatullah Callaghan, Paul Univ Windsor Sch Comp Sci Windsor ON N9B 3P4 Canada Univ Durham Dept Comp Sci Durham DH1 3HP England

ISBN: (纸本)9783540774419

parser combinators are higher-order functions used to build parsers as executable specifications of grammars. Some existing implementations are only able to handle limited ambiguity, some have exponential time and/or space complexity for ambiguous input, most cannot accommodate left-recursive grammars. This paper describes combinators, implemented in Haskell, which overcome all of these limitations.

关键词： parser combinators ambiguity left recursion functional programming natural-language parsing

来源：评论

学校读者我要写书评

暂无评论

Efficient parsing with parser combinators

引用

SCIENCE OF COMPUTER PROGRAMMING 2018年 161卷 57-88页

作者： Kurs, Jan Vrany, Jan Ghafari, Mohammad Lungu, Mircea Nierstrasz, Oscar Univ Bern Software Composit Grp Bern Switzerland Czech Tech Univ Software Engn Grp Prague Czech Republic Univ Groningen Software Engn & Architecture Grp Groningen Netherlands

parser combinators offer a universal and flexible approach to parsing. They follow the structure of an underlying grammar, are modular, well-structured, easy to maintain, and can recognize a large variety of languages including context-sensitive ones. However, these advantages introduce a noticeable performance overhead mainly because the same powerful parsing algorithm is used to recognize even simple languages. Time-wise, parser combinators cannot compete with parsers generated by well-performing parser generators or optimized hand-written code. Techniques exist to achieve a linear asymptotic performance of parser combinators, yet there is a significant constant multiplier. The multiplier can be lowered to some degree, but this requires advanced meta-programming techniques, such as staging or macros, that depend heavily on the underlying language technology. In this work we present a language-agnostic solution. We optimize the performance of parsing combinators with specializations of parsing strategies. For each combinator, we analyze the language parsed by the combinator and choose the most efficient parsing strategy. By adapting a parsing strategy for different parser combinators we achieve performance comparable to that of hand-written or optimized parsers while preserving the advantages of parsers combinators. (C) 2017 Elsevier B.V. All rights reserved.

关键词： Optimizations Parsing expression grammars parser combinators

来源：评论

学校读者我要写书评

暂无评论

Syntax Error Search Using parser combinators

Syntax Error Search Using Parser Combinators

引用

IEEE Conference of Russian Young Researchers in Electrical and Electronic Engineering (ElConRus)

作者： Kuznetsov, Mikhail Firsov, Georgii Natl Res Nucl Univ MEPhI Moscow Engn Phys Inst Moscow Russia

ISBN: (纸本)9781665404761

parser combinators is a popular approach to parsing sequences generated by context-free grammars, which can be specialized data formats (e.g. JSON, YAML), markup languages like XML or HTML. At the same time, this approach is rarely used for parsing programming languages. The purpose of this paper is to study the application of parser combinators for programming languages processing, and more precisely for searching of syntax errors. The method that had been developed during this research was compared with an algorithm of syntax analysis of programming languages using parser-generators. parser combinator takes less time on average to find a syntax error in the source code. Its average time complexity is linear with respect to the length of the input sequence, while the parser generator has an average quadratic complexity. Moreover, a parser combinator requires less memory than a parser generator. These results can be used for building intelligent code completion tools for fast syntax error detection.

关键词： programming languages syntax analysis parser combinators parser generators error searching

来源：评论

学校读者我要写书评

暂无评论

Graph parser combinators

引用

19th International Symposium on Implementation and Application of Functional Languages

作者： Mazanek, Steffen Minas, Mark Univ Bundeswehr Munich Germany

ISBN: (纸本)9783540853725

A graph language can be described by a graph grammar in a manner similar to a string grammar known from the theory of formal languages. Unfortunately, graph parsing is known to be computationally expensive in general. There are quite simple graph languages that crush most general-purpose graph parsers. In this paper we present graph parser combinators, a new approach to graph parsing inspired by the well-known string parser combinators. The basic idea is to define primitive graph parsers for elementary graph components and a set of combinators for the construction of more advanced graph parsers. Using graph parser combinators special-purpose graph parsers can be composed conveniently. Thereby, language-specific performance optimizations can be incorporated in a flexible manner.

关键词： functional programming graph parsing parser combinators visual languages

来源：评论

学校读者我要写书评

暂无评论

Practical, General parser combinators 16

Practical, General Parser Combinators

引用

ACM SIGPLAN Workshop on Partial Evaluation and Program Manipulation (PEPM)

作者： Izmaylova, Anastasia Afroozeh, Ali van der Storm, Tijs Ctr Wiskunde & Informat Amsterdam Netherlands

ISBN: (纸本)9781450340977

parser combinators are a popular approach to parsing where context-free grammars are represented as executable code. However, conventional parser combinators do not support left recursion, and can have worst-case exponential runtime. These limitations hinder the expressivity and performance predictability of parser combinators when constructing parsers for programming languages. In this paper we present general parser combinators that support all context-free grammars and construct a parse forest in cubic time and space in the worst case, while behaving nearly linearly on grammars of real programming languages. Our general parser combinators are based on earlier work on memoized Continuation-Passing Style (CPS) recognizers. First, we extend this work to achieve recognition in cubic time. Second, we extend the resulting cubic CPS recognizers to parsers that construct a binarized Shared Packed Parse Forest (SPPF). Our general parser combinators bring the best of both worlds: the flexibility and extensibility of conventional parser combinators and the expressivity and performance guarantees of general parsing algorithms. We used the approach presented in this paper as the basis for Meerkat, a general parser combinator library for Scala.

关键词： parser combinators general parsing left recursion continuation-passing style memoization higher-order functions

来源：评论

学校读者我要写书评

暂无评论

A New View on parser combinators 31

A New View on Parser Combinators

引用

31st Symposium on Implementation and Application of Functional Languages (IFL)

作者： Koopman, Pieter Plasmeijer, Rinus Radboud Univ Nijmegen Nijmegen Netherlands

ISBN: (纸本)9781450375627

parser combinators offer a concise and fast way to produce reasonably efficient parsers. The combinator libraries themselves can be small and provide an elegant application of functional programming techniques. They are one of the success stories in functional programming that are also ported to many other languages. In this paper, we illustrate that we can make the parser combinators more general by modeling them as a tagless domain specific language. The idea is to replace the ordinary combinators by a set of type constructor classes. By making different implementations of this class we can assign various interpretations of one and the same grammar specification. The set of type classes makes the DSL type-safe and extendable without needing to change existing parts and implementations. This enables us to make multiple interpretations, views, of the specified grammar. In this paper we show views for deterministic parsing, nondeterministic parsing, generating possible parse trees produced by the grammar without needing the corresponding input, generating inputs accepted by the grammar, adapting the grammar rules such that the parser combinators can handle left-recursion and so on. This makes our multi-view parser combinators more powerful than the existing approaches.

关键词： parser combinators Domain Specific Language Tagless

来源：评论

学校读者我要写书评

暂无评论

Design Patterns for parser combinators (Functional Pearl) 14

Design Patterns for Parser Combinators (Functional Pearl)

引用

14th ACM SIGPLAN International Symposium on Haskell (Haskell)

作者： Willis, Jamie Wu, Nicolas Imperial Coll London London England

ISBN: (纸本)9781450386159

parser combinators are a popular and elegant approach for parsing in functional languages. The design and implementation of such libraries are well discussed, but having a well-designed library is only one-half of the story. In this paper we explore several reusable approaches to writing parsers in combinator style, focusing on easy to apply patterns to keep parsing code simple, separated, and maintainable.

关键词： parser combinators

来源：评论

学校读者我要写书评

暂无评论

Total parser combinators 10

Total Parser Combinators

引用

15th ACM SIGPLAN International Conference on Functional Programming

作者： Danielsson, Nils Anders Univ Nottingham Sch Comp Sci Nottingham NG7 2RD England

ISBN: (纸本)9781605587943

A monadic parser combinator library which guarantees termination of parsing, while still allowing many forms of left recursion, is described. The library's interface is similar to those of many other parser combinator libraries, with two important differences: one is that the interface clearly specifies which parts of the constructed parsers may be infinite, and which parts have to be finite, using dependent types and a combination of induction and coinduction;and the other is that the parser type is unusually informative. The library comes with a formal semantics, using which it is proved that the parser combinators are as expressive as possible. The implementation is supported by a machine-checked correctness proof.

关键词： Dependent types mixed induction and coinduction parser combinators productivity termination

来源：评论

学校读者我要写书评

暂无评论

Staged parser combinators for Efficient Data Processing 14

Staged Parser Combinators for Efficient Data Processing

引用

2014 ACM International Conference on Object-Oriented-Programming-Systems-Languages-and-Applications (OOPSLA 14)

作者： Jonnalagedda, Manohar Coppey, Thierry Stucki, Sandro Rompf, Tiark Odersky, Martin EPFL LAMP Zurich Switzerland EPFL DATA Zurich Switzerland

ISBN: (纸本)9781450325851

parsers are ubiquitous in computing, and many applications depend on their performance for decoding data efficiently. parser combinators are an intuitive tool for writing parsers: tight integration with the host language enables grammar specifications to be interleaved with processing of parse results. Unfortunately, parser combinators are typically slow due to the high overhead of the host language abstraction mechanisms that enable composition. We present a technique for eliminating such overhead. We use staging, a form of runtime code generation, to dissociate input parsing from parser composition, and eliminate intermediate data structures and computations associated with parser composition at staging time. A key challenge is to maintain support for input dependent grammars, which have no clear stage distinction. Our approach applies to top-down recursive-descent parsers as well as bottom-up nondeterministic parsers with key applications in dynamic programming on sequences, where we auto-generate code for parallel hardware. We achieve performance comparable to specialized, hand-written parsers.

关键词： parser combinators multi-stage programming algebraic dynamic programming

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：