Standard

Parser combinators for context-free path querying. / Kirillov, Ilya; Nozkin, Ilya; Grigorev, Semyon.

Scala 2018 - Proceedings of the 9th ACM SIGPLAN International Symposium on Scala, co-located with ICFP 2018. ed. / Sebastian Erdweg; Bruno C. D. S. Oliveira. Association for Computing Machinery, 2018. p. 13-23 (Scala 2018 - Proceedings of the 9th ACM SIGPLAN International Symposium on Scala, co-located with ICFP 2018).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review

Harvard

Kirillov, I, Nozkin, I & Grigorev, S 2018, Parser combinators for context-free path querying. in S Erdweg & BCDS Oliveira (eds), Scala 2018 - Proceedings of the 9th ACM SIGPLAN International Symposium on Scala, co-located with ICFP 2018. Scala 2018 - Proceedings of the 9th ACM SIGPLAN International Symposium on Scala, co-located with ICFP 2018, Association for Computing Machinery, pp. 13-23, 9th ACM SIGPLAN International Symposium on Scala, Scala 2018, Part of the ACM SIGPLAN International Conference on Functional Programming, ICFP 2018, St. Louis, United States, 28/09/18. https://doi.org/10.1145/3241653.3241655

APA

Kirillov, I., Nozkin, I., & Grigorev, S. (2018). Parser combinators for context-free path querying. In S. Erdweg, & B. C. D. S. Oliveira (Eds.), Scala 2018 - Proceedings of the 9th ACM SIGPLAN International Symposium on Scala, co-located with ICFP 2018 (pp. 13-23). (Scala 2018 - Proceedings of the 9th ACM SIGPLAN International Symposium on Scala, co-located with ICFP 2018). Association for Computing Machinery. https://doi.org/10.1145/3241653.3241655

Vancouver

Kirillov I, Nozkin I, Grigorev S. Parser combinators for context-free path querying. In Erdweg S, Oliveira BCDS, editors, Scala 2018 - Proceedings of the 9th ACM SIGPLAN International Symposium on Scala, co-located with ICFP 2018. Association for Computing Machinery. 2018. p. 13-23. (Scala 2018 - Proceedings of the 9th ACM SIGPLAN International Symposium on Scala, co-located with ICFP 2018). https://doi.org/10.1145/3241653.3241655

Author

Kirillov, Ilya ; Nozkin, Ilya ; Grigorev, Semyon. / Parser combinators for context-free path querying. Scala 2018 - Proceedings of the 9th ACM SIGPLAN International Symposium on Scala, co-located with ICFP 2018. editor / Sebastian Erdweg ; Bruno C. D. S. Oliveira. Association for Computing Machinery, 2018. pp. 13-23 (Scala 2018 - Proceedings of the 9th ACM SIGPLAN International Symposium on Scala, co-located with ICFP 2018).

BibTeX

@inproceedings{1f232eb2c2e04b479621e2fe3101402a,
title = "Parser combinators for context-free path querying",
abstract = "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.",
keywords = "Context-Free Language Reachability, Context-Free Path Querying, Generalized LL, GLL, Graph Databases, Language-Constrained Path Problem, Neo4j, Parser Combinators, Scala",
author = "Ilya Kirillov and Ilya Nozkin and Semyon Grigorev",
year = "2018",
month = sep,
day = "17",
doi = "10.1145/3241653.3241655",
language = "English",
series = "Scala 2018 - Proceedings of the 9th ACM SIGPLAN International Symposium on Scala, co-located with ICFP 2018",
publisher = "Association for Computing Machinery",
pages = "13--23",
editor = "Sebastian Erdweg and Oliveira, {Bruno C. D. S.}",
booktitle = "Scala 2018 - Proceedings of the 9th ACM SIGPLAN International Symposium on Scala, co-located with ICFP 2018",
address = "United States",
note = "9th ACM SIGPLAN International Symposium on Scala, Scala 2018, Part of the ACM SIGPLAN International Conference on Functional Programming, ICFP 2018 ; Conference date: 28-09-2018",

}

RIS

TY - GEN

T1 - Parser combinators for context-free path querying

AU - Kirillov, Ilya

AU - Nozkin, Ilya

AU - Grigorev, Semyon

PY - 2018/9/17

Y1 - 2018/9/17

N2 - 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.

AB - 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.

KW - Context-Free Language Reachability

KW - Context-Free Path Querying

KW - Generalized LL

KW - GLL

KW - Graph Databases

KW - Language-Constrained Path Problem

KW - Neo4j

KW - Parser Combinators

KW - Scala

UR - http://www.scopus.com/inward/record.url?scp=85056744255&partnerID=8YFLogxK

U2 - 10.1145/3241653.3241655

DO - 10.1145/3241653.3241655

M3 - Conference contribution

AN - SCOPUS:85056744255

T3 - Scala 2018 - Proceedings of the 9th ACM SIGPLAN International Symposium on Scala, co-located with ICFP 2018

SP - 13

EP - 23

BT - Scala 2018 - Proceedings of the 9th ACM SIGPLAN International Symposium on Scala, co-located with ICFP 2018

A2 - Erdweg, Sebastian

A2 - Oliveira, Bruno C. D. S.

PB - Association for Computing Machinery

T2 - 9th ACM SIGPLAN International Symposium on Scala, Scala 2018, Part of the ACM SIGPLAN International Conference on Functional Programming, ICFP 2018

Y2 - 28 September 2018

ER -

ID: 48534826