• Conjunctive languages are useful for static code analysis: Context-Sensitive Data-Dependence Analysis
  via Linear Conjunctive Language Reachability
• It is possible to support conjunction in parser-combinators for linear input.
  • code
  • paper in Ru
• Is it possible to support conjunction in parser combinators for graphs? The precise solution is impossible, so it is necessary to guarantee overapproximation.

Meerkat supports semantic code specification, but it works only if the result of parsing is an SPPF with a single tree. SPPF is a compressed representation of parse forest. In case of graph parsing, we get an arbitrary SPPF which can contains an infinite set of trees. One of the possible solutions is lazy tree extraction. For each tree semantic code can be calculated by using existing methods. The result is a lazy collection of semantic values for each tree from SPPF.

• Implement BFS-based lazy trees extraction.
• Implement the interface for a user, which provides an ability to calculate semantic code for arbitrary parsing result.
• Implement tests.

Implement taint analysis upon CFL reachability (which is implemented in this library) as a plugin for IDEA.

• As a solution for this task
• Scalable and Precise Taint Analysis for Android
• CFL reachability

Create an interface for input data.

• Generalization of linear and graph-structured data
• Should be as general as possible
  Seems, that next functions are required.
• Get outgoing tokens by position
• Convert edg label to token
• Convert vrt label to token

При использовании Meerkat были обнаружены несколько ошибок:

1. toDot.visit не умеет работать с циклами, возникает StackOverflowError
2. SPPFToTrees не работает
3. Нельзя выбрать стартовую вершину в графе (всегда с 0 должен начинаться)

trait Input[-L] {
  type M >: L
  type Edge = (M, Int)

  def length: Int

  def start: Int = 0

...

Все проверялось при таких данных https://gist.github.com/simonvar/5bbc9fba89af239552ba7c1555714468

Implement a distributed version of Meerkat. It is necessary for huge graphs parsing. (Synchronize with this task)

• Naive graph partitioning (for the first step).
• Implement distributed version of GLL. Without SPPF for the first step. It is necessary to share descriptors for border vertices. The main problem is a GSS sharing because descriptor contains a reference to GSS node. Seems, that GSS can be filtered such that it contains only vertices which reachable from descriptors which should be shared.
• Testing. Create good test base.
• Optimal graph partitioning. Synchronize with this issue.
• Evaluation. Example of big RDF
• Version with SPPF.

Prepare data and queries from articles. Possible, not from all. Some of the listed articles have a strange evaluation. So, briefly read them all and select articles with reproducible evaluation. Request authors for access to data which used for evaluation if necessary.

• Precise interprocedural dataflow analysis via graph reachability
• T. W. Reps, S. Horwitz, S. Sagiv, and G. Rosay. Speeding up slicing
• T. W. Reps. Shape analysis as a generalized path problem.
• Specification Inference Using Context-Free Language Reachability
• Existential Label Flow Inference via CFL Reachability
• Type-base flow analysis: from polymorphic subtyping to CFL-reachability
• Refinement-based context-sensitive points-to analysis for Java
• Demand-driven context-sensitive alias analysis for Java
• Efficient subcubic alias analysis for C
• Demand-driven alias analysis for C

Реализовать на Scala библиотеку парсер-комбинаторов. Снабдить её тестами и примерами. Опубликовать на github. Ссылку на репозиторий оставлять в комментариях к этой таске. Вопросы задавать там же.

• Merge changes from https://github.com/sofysmol/Meerkat
• Merge changes from https://github.com/meerkat-parser/Meerkat
• CI build (issue #1)
• More tests
• Integration with Neo4J
• Create examples of real data and real queries, evaluate.

• Unified interface for graph-structured data querying: #21
• Documentation (github.io): #27
• Automated release porcess: #30
• Parallel query processing (single machine, shared memory): #25
• Destributed query processing: #24
• Conjunctive languages support: #26

Для тех, кто хочет заниматься задачей #54.

На языке программрования Scala создайте приложение, которое генерирует случайны граф с не менее чем 10000 вершин и 1000000 рёбер, сохраняет его в Neo4j, а затем выполняет несколько (не меньше 3) различных запросов на поиск пути к нему. Вы можете использовать любые доступные средства интеграции Neo4j и Scala.

Результат: ссылка на репозиторий с реализацией. Репозитроий должен быть снабжён всем необходимым для сборки и запуска приложения.

Create project site (github.io)

• Project description
• Examples
• Documentation

• Create an image of Neo4j, which contains data from this data set.
• Implement ability to switch between two modes of query evaluation: with SPPF and without SPPF.
• Implement queries from the dataset mentioned above.
• Do performance evaluation.
• Create examples, which demonstrates features of combinators
  • Composability
  • Type safety
  • Semantic actions specification (look at #5)

Try to implement a parallel version of GLL. Is it possible without tons of locks on all share data structures? Can it be really faster than sequential GLL?

Provide user-friendly representation of SPPF:

• Set of triples
• Lazy collection of trees
• Lazy collection of paths (the path is a yield of the tree, so implement previous first)

Travis provides integration with a wide range of deployment services: https://docs.travis-ci.com/user/deployment/

It would be great to automate the publishing of stable builds results.

• List of builds/jars on the separated GitHub page with automated update
• Automated versioning of CI build artifacts
• Automated release process: versioning, tag creation, binaries publishing, release notes creation

Configure Travis CI build (howto).

Create an adapter for JGraphT library.

• Use JGraphT graph as a data source. labels of vertices and edges may be an arbitrary type.
• Provide user-friendly representation of query result. Look at #22. Note that paths should be constructed in terms of the input graph.

• An example of context-free query in OpenCypger