Interval Parsing Grammars for File Format Parsing (paper) (dl.acm.org)

submitted 2 months ago by armchair_progamer@programming.dev to c/programming_languages@programming.dev

0 comments fedilink hide all child comments

Abstract:

File formats specify how data is encoded for persistent storage. They cannot be formalized as context-free grammars since their specifications include context-sensitive patterns such as the random access pattern and the type-length-value pattern. We propose a new grammar mechanism called Interval Parsing Grammars IPGs) for file format specifications. An IPG attaches to every nonterminal/terminal an interval, which specifies the range of input the nonterminal/terminal consumes. By connecting intervals and attributes, the context-sensitive patterns in file formats can be well handled. In this paper, we formalize IPGs' syntax as well as its semantics, and its semantics naturally leads to a parser generator that generates a recursive-descent parser from an IPG. In general, IPGs are declarative, modular, and enable termination checking. We have used IPGs to specify a number of file formats including ZIP, ELF, GIF, PE, and part of PDF; we have also evaluated the performance of the generated parsers.

no comments (yet)

sorted by: hot top controversial new old

there doesn't seem to be anything here

this post was submitted on 10 Aug 2024

2 points (100.0% liked)

Programming Languages

1159 readers

1 users here now

Hello!

This is the current Lemmy equivalent of https://www.reddit.com/r/ProgrammingLanguages/.

The content and rules are the same here as they are over there. Taken directly from the /r/ProgrammingLanguages overview:

This community is dedicated to the theory, design and implementation of programming languages.

Be nice to each other. Flame wars and rants are not welcomed. Please also put some effort into your post.

This isn't the right place to ask questions such as "What language should I use for X", "what language should I learn", and "what's your favorite language". Such questions should be posted in /c/learn_programming or /c/programming.

This is the right place for posts like the following:

"Check out this new language I've been working on!"
"Here's a blog post on how I implemented static type checking into this compiler"
"I want to write a compiler, where do I start?"
"How does the Java compiler work? How does it handle forward declarations/imports/targeting multiple platforms/?"
"How should I test my compiler? How are other compilers and interpreters like gcc, Java, and python tested?"
"What are the pros/cons of ?"
"Compare and contrast vs. "
"Confused about the semantics of this language"
"Proceedings from PLDI / OOPSLA / ICFP / "

See /r/ProgrammingLanguages for specific examples

Related online communities

founded 1 year ago

MODERATORS

armchair_progamer@programming.dev