blob: 8347a59faae5395d3c58a08119b62a63e457ee88 (
plain) (
blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
|
SPELL=pacc
VERSION=0.3
SOURCE="$SPELL-$VERSION.tar.bz2"
SOURCE_URL[0]=https://static.paccrat.org/release/$SOURCE
SOURCE_HASH=sha512:b6f3cadf2ecc96a41a04558e6b8d9d4c55bba15b467c9a9354e51f6fe62898e4753321cceee14d9c8c84000381b64b3db3bd89793e9c27dd2c795fd4847194bb
SOURCE_DIRECTORY="$BUILD_DIRECTORY/$SPELL-$VERSION"
WEB_SITE="https://paccrat.org/"
LICENSE[0]="GPL-3.0-only"
ENTERED=20190801
KEYWORDS=""
SHORT="a compiler-compiler"
cat << EOF
pacc is a compiler-compiler, somewhat like yacc (or bison). Its input is a
description of a grammar, and its output is a C function that recognizes
strings of that grammar. The significant technical difference is this:
yacc reads a context-free grammar (CFGs), and writes a LALR(1) parser;
pacc reads a parsing expression grammar (PEG), and writes a packrat parser.
PEGs and packrat parsing offer several advantages over CFGs.
* There is no need for a two-level structure with a separate lexer (this is
essentially a misfeature of CFGs - they are unable to express standard
tokenization rules naturally).
* PEGs can “look ahead” in the input as far as they need to. * Despite
arbitrary look-ahead, packrat parsers are linear in time and
space complexity: O(n) in the size of the input (whereas LALR(1) parsers
are O(n²), and fully general CFG parsing is O(n³)).
* PEGs are easy to understand, and pleasant to work with.
EOF
|
