Content deleted Content added
citation |
→As pseudocode: fixed pseudocode |
||
Line 26:
'''let''' the grammar contain ''r'' nonterminal symbols ''R''<sub>1</sub> ... ''R''<sub>''r''</sub>, with start symbol ''R''<sub>1</sub>.
'''let''' ''P''[''n'',''n'',''r''] be an array of booleans. Initialize all elements of ''P'' to false.
'''let''' ''back''[''n'',''n'',''r''] be an array of lists of backpointing triples. Initialize all elements of ''back'' to the empty list.
'''for each''' ''s'' = 1 to ''n''
Line 35 ⟶ 36:
'''for each''' ''p'' = 1 to ''l''-1 ''-- Partition of span''
'''for each''' production ''R''<sub>''a''</sub> → ''R''<sub>''b''</sub> ''R''<sub>''c''</sub>
'''if''' ''P''[''p'',''s'',''b''] and ''P''[''l''-''p'',''s''+''p'',''c''] '''then'''
'''set''' ''P''[''l'',''s'',''a''] = true, append <p,b,c> to ''back''[''l'',''s'',''a'']
'''if''' ''P''[n,''1'',''1''] is true '''then'''
''I'' is member of language
return ''back'' -- by ''retracing the steps through back, one can easily construct all possible parse trees of the string.''
'''else'''
''
<div class="toccolours mw-collapsible mw-collapsed">
Line 63 ⟶ 67:
'''set''' ''P''[''l'',''s'',''a''] = prob_splitting
'''set''' ''back''[''l'',''s'',''a''] = <p,b,c>
'''if''' ''P''[n,''1'',''1''] > 0 '''then'''
find the parse tree by retracing through ''back''
return the parse tree
'''else'''
'''return''' "not a member of language"
</div>
</div>
| |||