10000 Issue #1388 is ready for review. · lark-parser/lark@daac65d · GitHub
[go: up one dir, main page]
Skip to content

Commit daac65d

Browse files
RossPattersonRossPatterson
committed
Issue #1388 is ready for review.
1 parent 40576d2 commit daac65d

10 files changed

+682
-762
lines changed

‎lark/grammars/lark.lark

Lines changed: 4 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -1,17 +1,15 @@
11
# Lark grammar of Lark's syntax
22
# Note: Lark is not bootstrapped, its parser is implemented in load_grammar.py
33
# This grammar matches that one, but does not enfore some rules that it does.
4-
# If you want to enforce those, you can pass the "LarkValidatorVisitor" over
4+
# If you want to enforce those, you can pass the "LarkValidator" over
55
# the parse tree, like this:
66

7-
# import os
8-
# import lark
9-
# from lark.lark_validator_visitor import LarkValidatorVisitor
7+
# from lark import Lark
8+
# from lark.lark_validator import LarkValidator
109
#
11-
# lark_path = os.path.join(os.path.dirname(lark.__file__), 'grammars/lark.lark')
1210
# lark_parser = Lark.open_from_package("lark", "grammars/lark.lark", parser="lalr")
1311
# parse_tree = lark_parser.parse(my_grammar)
14-
# LarkValidatorVisitor.validate(parse_tree)
12+
# LarkValidator.validate(parse_tree)
1513

1614
start: (_item? _NL)* _item?
1715

‎lark/lark_validator.py

Lines changed: 265 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,265 @@
1+
from typing import Any, Dict, List
2+
3+
from .exceptions import GrammarError
4+
from .grammar import TOKEN_DEFAULT_PRIORITY, RuleOptions
5+
from .lexer import Token
6+
from .load_grammar import eval_escaping
7+
from .tree import Tree
8+
9+
class Definition:
10+
def __init__(self, is_term, tree, params=(), options=None):
11+
self.is_term = is_term
12+
self.tree = tree
13+
self.params = tuple(params)
14+
15+
class LarkValidator:
16+
17+
@classmethod
18+
def validate(cls, tree: Tree, options: Dict[str, Any] = {}):
19+
visitor = cls(tree, options)
20+
visitor._cross_check_symbols()
21+
visitor._resolve_term_references()
22+
visitor._check_literals(tree)
23+
return tree
24+
25+
def __init__(self, tree: Tree, options: Dict[str, Any]):
26+
self._definitions: Dict[str, Definition] = {}
27+
self._ignore_names: List[str] = []
28+
self._load_grammar(tree)
29+
30+
def _check_literals(self, tree: Tree) -> None:
31+
for literal in tree.find_data("literal"):
32+
self._literal(literal)
33+
34+
def _cross_check_symbols(self) -> None:
35+
# Based on load_grammar.GrammarBuilder.validate()
36+
for name, d in self._definitions.items():
37+
params = d.params
38+
definition = d.tree
39+
for i, p in enumerate(params):
40+
if p in self._definitions:
41+
raise GrammarError("Template Parameter conflicts with rule %s (in template %s)" % (p, name))
42+
if p in params[:i]:
43+
raise GrammarError("Duplicate Template Parameter %s (in template %s)" % (p, name))
44+
# Remaining checks don't apply to abstract rules/terminals (i.e., created with %declare)
45+
if definition and isinstance(definition, Tree):
46+
for template in definition.find_data('template_usage'):
47+
if d.is_term:
48+
raise GrammarError("Templates not allowed in terminals")
49+
sym = template.children[0].data
50+
args = template.children[1:]
51+
if sym not in params:
52+
if sym not in self._definitions:
53+
raise GrammarError(f"Template '{sym}' used but not defined (in {('rule', 'terminal')[d.is_term]} {name})")
54+
if len(args) != len(self._definitions[sym].params):
55+
expected, actual = len(self._definitions[sym].params), len(args)
56+
raise GrammarError(f"Wrong number of template arguments used for {expected} "
57+
f"(expected {expected}, got {actual}) (in {('rule', 'terminal')[d.is_term]} {actual})")
58+
for sym in _find_used_symbols(definition):
59+
if sym not in self._definitions and sym not in params:
60+
raise GrammarError(f"{('Rule', 'Terminal')[sym.isupper()]} '{sym}' used but not defined (in {('rule', 'terminal')[d.is_term]} { name})")
61+
if not set(self._definitions).issuperset(self._ignore_names):
62+
raise GrammarError("Terminals %s were marked to ignore but were not defined!" % (set(self._ignore_names) - set(self._definitions)))
63+
64+
def _declare(self, stmt: Tree) -> None:
65+
for symbol in stmt.children:
66+
if isinstance(symbol, Tree) and symbol.data == 'name':
67+
symbol = symbol.children[0]
68+
if not isinstance(symbol, Token) or symbol.type != "TOKEN":
69+
raise GrammarError("Expecting terminal name")
70+
self._define(symbol.value, True, None)
71+
72+
def _define(self, name: str, is_term: bool, exp: "Tree|None", params: List[str] = [], options:Any = None, *, override: bool = False, extend: bool = False) -> None:
73+
# Based on load_grammar.GrammarBuilder._define()
74+
if name in self._definitions:
75+
if not override and not extend:
76+
raise GrammarError(f"{('Rule', 'Terminal')[is_term]} '{name}' defined more than once")
77+
if extend:
78+
base_def = self._definitions[name]
79+
if is_term != base_def.is_term:
80+
raise GrammarError("fCannot extend {('rule', 'terminal')[is_term]} {name} - one is a terminal, while the other is not.")
81+
if tuple(params) != base_def.params:
82+
raise GrammarError(f"Cannot extend {('rule', 'terminal')[is_term]} with different parameters: {name}")
83+
if base_def.tree is None:
84+
raise GrammarError(f"Can't extend {('rule', 'terminal')[is_term]} {name} - it is abstract.")
85+
if name.startswith('__'):
86+
raise GrammarError(f'Names starting with double-underscore are reserved (Error at {name})')
87+
if is_term:
88+
if options and not isinstance(options, int):
89+
raise GrammarError(f"Terminal require a single int as 'options' (e.g. priority), got {type(options)}")
90+
else:
91+
if options and not isinstance(options, RuleOptions):
92+
raise GrammarError("Rules require a RuleOptions instance as 'options'")
93+
self._definitions[name] = Definition(is_term, exp, params)
94+
95+
def _extend(self, stmt: Tree) -> None:
96+
definition = stmt.children[0]
97+
if definition.data == 'token':
98+
name = definition.children[0]
99+
if name not in self._definitions:
100+
raise GrammarError(f"Can't extend terminal {name} as it wasn't defined before")
101+
self._token(definition, extend=True)
102+
else: # definition.data == 'rule'
103+
name = definition.children[1]
104+
if name not in self._definitions:
105+
raise GrammarError(f"Can't extend rule {name} as it wasn't defined before")
106+
self._rule(definition, extend=True)
107+
108+
def _ignore(self, stmt: Tree) -> None:
109+
# Children: expansions
110+
# - or -
111+
# Children: token
112+
exp_or_name = stmt.children[0]
113+
if isinstance(exp_or_name, str):
114+
self._ignore_names.append(exp_or_name)
115+
else:
116+
assert isinstance(exp_or_name, Tree)
117+
t = exp_or_name
118+
if t.data == 'expansions' and len(t.children) == 1:
119+
t2 ,= t.children
120+
if t2.data=='expansion':
121+
if len(t2.children) > 1:
122+
raise GrammarError("Bad %ignore - must have a Terminal or other value.")
123+
item ,= t2.children
124+
if item.data == 'value':
125+
item ,= item.children
126+
if isinstance(item, Token):
127+
# Keep terminal name, no need to create a new definition
128+
self._ignore_names.append(item.value)
129+
return
130+
if item.data == 'name':
131+
token ,= item.children
132+
if isinstance(token, Token) and token.type == "TOKEN":
133+
# Keep terminal name, no need to create a new definition
134+
self._ignore_names.append(token.value)
135+
return
136+
name = '__IGNORE_%d'% len(self._ignore_names)
137+
self._ignore_names.append(name)
138+
self._definitions[name] = Definition(True, t, options=TOKEN_DEFAULT_PRIORITY)
139+
140+
def _literal(self, tree: Tree) -> None:
141+
# Based on load_grammar.GrammarBuilder.literal_to_pattern().
142+
assert tree.data == 'literal'
143+
literal = tree.children[0]
144+
assert isinstance(literal, Token)
145+
v = literal.value
146+
flag_start = max(v.rfind('/'), v.rfind('"'))+1
147+
assert flag_start > 0
148+
flags = v[flag_start:]
149+
if literal.type == 'STRING' and '\n' in v:
150+
raise GrammarError('You cannot put newlines in string literals')
151+
if literal.type == 'REGEXP' and '\n' in v and 'x' not in flags:
152+
raise GrammarError('You can only use newlines in regular expressions '
153+
'with the `x` (verbose) flag')
154+
v = v[:flag_start]
155+
assert v[0] == v[-1] and v[0] in '"/'
156+
x = v[1:-1]
157+
s = eval_escaping(x)
158+
if s == "":
159+
raise GrammarError("Empty terminals are not allowed (%s)" % literal)
160+
161+
def _load_grammar(self, tree: Tree) -> None:
162+
for stmt in tree.children:
163+
if stmt.data == 'declare':
164+
self._declare(stmt)
165+
elif stmt.data == 'extend':
166+
self._extend(stmt)
167+
elif stmt.data == 'ignore':
168+
self._ignore(stmt)
169+
elif stmt.data in ['import', 'multi_import']:
170+
# TODO How can we process imports in the validator?
171+
pass
172+
elif stmt.data == 'override':
173+
self._override(stmt)
174+
elif stmt.data == 'rule':
175+
self._rule(stmt)
176+
elif stmt.data == 'token':
177+
self._token(stmt)
178+
else:
179+
assert False, f"Unknown statement type: {stmt}"
180+
181+
def _override(self, stmt: Tree) -> None:
182+
definition = stmt.children[0]
183+
if definition.data == 'token':
184+
name = definition.children[0]
185+
if name not in self._definitions:
186+
raise GrammarError(f"Cannot override a nonexisting terminal {name}")
187+
self._token(definition, override=True)
188+
else: # definition.data == 'rule'
189+
name = definition.children[1]
190+
if name not in self._definitions:
191+
raise GrammarError(f"Cannot override a nonexisting rule {name}")
192+
self._rule(definition, override=True)
193+
194+
def _resolve_term_references(self) -> None:
195+
# Based on load_grammar.resolve_term_references()
196+
# and the bottom of load_grammar.GrammarBuilder.load_grammar()
197+
term_dict = { name: d.tree
198+
for name, d in self._definitions.items()
199+
if d.is_term
200+
}
201+
while True:
202+
changed = False
203+
for name, token_tree in term_dict.items():
204+
if token_tree is None: # Terminal added through %declare
205+
continue
206+
for exp in token_tree.find_data('value'):
207+
item ,= exp.children
208+
if isinstance(item, Tree) and item.data == 'name' and isinstance(item.children[0], Token) and item.children[0].type == 'RULE' :
209+
raise GrammarError("Rules aren't allowed inside terminals (%s in %s)" % (item, name))
210+
elif isinstance(item, Token):
211+
try:
212+
term_value = term_dict[item.value]
213+
except KeyError:
214+
raise GrammarError("Terminal used but not defined: %s" % item.value)
215+
assert term_value is not None
216+
exp.children[0] = term_value
217+
changed = True
218+
else:
219+
assert isinstance(item, Tree)
220+
if not changed:
221+
break
222+
223+
for name, term in term_dict.items():
224+
if term: # Not just declared
225+
for child in term.children:
226+
ids = [id(x) for x in child.iter_subtrees()]
227+
if id(term) in ids:
228+
raise GrammarError("Recursion in terminal '%s' (recursion is only allowed in rules, not terminals)" % name)
229+
230+
def _rule(self, tree, override=False, extend=False) -> None:
231+
# Children: modifiers, name, params, priority, expansions
232+
name = tree.children[1]
233+
if tree.children[0].data == "rule_modifiers" and tree.children[0].children:
234+
modifiers = tree.children[0].children[0]
235+
if '?' in modifiers and name.startswith('_'):
236+
raise GrammarError("Inlined rules (_rule) cannot use the ?rule modifier.")
237+
if tree.children[2].children[0] is not None:
238+
params = [t.value for t in tree.children[2].children] # For the grammar parser
239+
else:
240+
params = []
241+
self._define(name, False, tree.children[4], params=params, override=override, extend=extend)
242+
243+
def _token(self, tree, override=False, extend=False) -> None:
244+
# Children: name, priority, expansions
245+
# - or -
246+
# Children: name, expansions
247+
if tree.children[1].data == "priority" and tree.children[1].children:
248+
opts = int(tree.children[1].children[0]) # priority
249+
else:
250+
opts = TOKEN_DEFAULT_PRIORITY
251+
for item in tree.children[-1].find_data('alias'):
252+
raise GrammarError("Aliasing not allowed in terminals (You used -> in the wrong place)")
253+
self._define(tree.children[0].value, True, tree.children[-1], [], opts, override=override, extend=extend)
254+
255+
def _find_used_symbols(tree) -> List[str]:
256+
# Based on load_grammar.GrammarBuilder._find_used_symbols()
257+
assert tree.data == 'expansions'
258+
results = []
259+
for expansion in tree.find_data('expansion'):
260+
for item in expansion.scan_values(lambda t: True):
261+
if isinstance(item, Tree) and item.data == 'name':
262+
results.append(item.data)
263+
elif isinstance(item, Token) and item.type not in ['NUMBER', 'OP', 'STRING', 'REGEXP']:
264+
results.append(item.value)
265+
return results

0 commit comments

Comments
 (0)
0