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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
|
NAME
wncstr -- general parsing and writing package
SYNOPSIS
#include "wncstr.h"
WN_PARSE
WN_WRITE
wn_make_cstream(&stream,pmove_block,move_block_ptr,
block_size,parse_or_write)
wn_cstream stream;
void (*pmove_block)(/* block,&actually_moved,request_moved,
move_block_ptr */);
ptr move_block_ptr;
int block_size,parse_or_write;
wn_free_cstream(stream)
wn_cstream stream;
int wn_current_mark(stream)
wn_cstream stream;
bool wn_set_current_mark(stream,mark)
wn_cstream stream;
int mark;
wn_flush_to_mark(stream,mark)
wn_cstream stream;
int mark;
bool wn_cstream_debug(stream)
wn_cstream stream;
DESCRIPTION
wncstr, wncstl, wnptok, wnwtok, wnwtokp, and wncinf comprise
an integrated package designed to parse and write complicated
files and strings. Parsing is accomplished using a generalized
recursive-descent methodology [1]; writing is accomplished
using a recursive-descent like methodology. Identical or very similar
grammars work for parsing and for writing a language. The C code
is also very similar. Very complicated grammars
can be parsed efficiently using this package, including context-free
grammars with long lookahead and many context-sensitive grammars.
No distinction is made between lexical analysis and parsing proper;
the lexical analysis is handled in the same way as the parsing.
The object to be parsed or written must first
be converted to a logical character array (a cstream).
"wn_make_cstream" accomplishes this in general; for files and
strings see wncstl for shortcuts. A cstream is logically an array of
characters (that is, bytes), together with a cursor or
"current mark". The current mark points to the character
currently being looked at. Thus, during parsing or writing,
the current mark moves from 0 (beginning of stream) to
larger and larger values and eventually reaches end of stream.
Parsing is accomplished using a generalized recursive-descent
methodology. Generally, you need a C subroutine for each non-terminal in
the grammar. The subroutine generally has 2 or more arguments
and returns a boolean. The first argument is the cstream to
parse; the other arguments are parse trees and other data constructed
if the parse succeeds; the return value says whether the parse
succeeded. When called, the subroutine attempts to parse the
non-terminal from the cstream, starting at the current mark.
If it fails, it returns FALSE and sets the current mark back
to its start value (using "wn_set_current_mark" and
"wn_current_mark"). If its succeeds, it returns TRUE,
usually generates some data (such as a parse tree), and
leaves the current mark after the parsed non-terminal in
the cstream. These subroutines are built from other
non-terminal parsing subroutines. The hierarchy bottoms out
with the subroutines in wnptok. Subroutines are often combined
in logical expressions.
All characters earlier in the cstream than the current mark
take up dynamic memory unless flushed using "wn_flush_to_mark".
Use "wn_flush_to_mark" when it is clear that characters before
"mark" will never be examined again.
"wn_cstream_debug" prints the characters from "stream" in the
neighborhood of the current mark. This information is very useful
for debugging parsers. "wn_cstream_debug" always returns TRUE, so
it can be inserted into logical expressions.
Writing is also accomplished with a recursive-descent like
methodology, with a subroutine for each non-terminal in the
grammar. The subroutine generally has 2 or more arguments;
no value is returned. The first argument is the cstream to
write into; the other arguments contain the information to write.
These subroutines are built from other non-terminal writing subroutines.
The hierarchy bottoms out with the subroutines in wnwtok and wnwtokp.
Generally, the same or similar subroutine hierarchies works for
parsing and writing a language.
Routines in wncinf assist in printing error messages with
line numbers.
Routines in wnscan scan a cstream for patterns.
BUGS
Too many subroutine names to remember.
This package may be slower than less general parsing packages.
SEE ALSO
wncstl, wnptok, wnscan, wnwtok, wnwtokp, wncinf
REFERENCES
[1] Alfred V. Aho, Jeffrey D. Ullman: Principles of Compiler Design,
April 1979, Addison-Wesley Publishing, Reading Massachusetts.
AUTHOR
Will Naylor
|
