Skip to content

Embed URL

HTTPS clone URL

Subversion checkout URL

You can clone with
or
.
Download ZIP
A stab at an [inefficient] GLR Parser, without tables (is this what "ascent-descent" is supposed to do?)
//Compiler: 1
using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
public struct Item : IEquatable<Item>
{
public Item(int rule, int symbol, string lookahead)
{
this.Rule = rule;
this.Symbol = symbol;
this.Lookahead = lookahead;
}
public readonly int Rule;
public readonly int Symbol;
public readonly string Lookahead;
public override bool Equals(object obj) { return obj != null && this.Equals((Item)obj); }
public Item Next() { return new Item(this.Rule, this.Symbol + 1, this.Lookahead); }
public bool Equals(Item other) { return this.Rule == other.Rule && this.Symbol == other.Symbol && this.Lookahead == other.Lookahead; }
public override int GetHashCode() { return this.Rule.GetHashCode() ^ this.Symbol.GetHashCode() ^ (this.Lookahead != null ? this.Lookahead.GetHashCode() : 0); }
public override string ToString() { return string.Format("Item {{Rule {0}, Symbol {1}}}", this.Rule, this.Symbol, this.Lookahead); }
}
public struct Production : IEnumerable<string>, IEquatable<Production>
{
public Production(string symbol, IList<string> values)
{
this.Symbol = symbol;
this.Values = values;
}
public readonly string Symbol;
private readonly IList<string> Values;
public IEnumerator<string> GetEnumerator() { IEnumerable<string> l = this.Values; return l.GetEnumerator(); }
IEnumerator IEnumerable.GetEnumerator() { return this.GetEnumerator(); }
public override bool Equals(object obj) { return obj != null && this.Equals((Production)obj) ; }
public bool Equals(Production other) { return this.Symbol == other.Symbol && Enumerable.SequenceEqual(this, other); }
public override int GetHashCode() { return this.Symbol.GetHashCode() ^ this.Select(s => s.GetHashCode()).Aggregate(0, (a, b) => a ^ b); }
public override string ToString() { return string.Format("{0}: {1}", this.Symbol, string.Join(" ", this.Values.ToArray())); }
public string this[int index] { get { return this.Values[index]; } }
}
public class ConsPair<T> : IEnumerable<T>
{
public readonly T Car;
public readonly ConsPair<T> Cdr;
public ConsPair(T car, ConsPair<T> cdr) { this.Car = car; this.Cdr = cdr; }
public IEnumerator<T> GetEnumerator() { for (var me = this; me != null; me = me.Cdr) { yield return me.Car; } }
IEnumerator IEnumerable.GetEnumerator() { return this.GetEnumerator(); }
public override string ToString() { return string.Format("[{0}]", string.Join(", ", new List<T>(this).ConvertAll(a => string.Format("{0}", a)).ToArray())); }
public ConsPair<T> Take(int n) { return n > 0 ? new ConsPair<T>(this.Car, n > 1 ? this.Cdr.Take(n - 1) : null) : null; }
public ConsPair<T> Reversed()
{
ConsPair<T> result = null;
for (var me = this; me != null; me = me.Cdr) { result = new ConsPair<T>(me.Car, result); }
return result;
}
public override bool Equals(object obj)
{
var other = obj as ConsPair<T>;
return EqualityComparer<T>.Default.Equals(other.Car, this.Car) && EqualityComparer<ConsPair<T>>.Default.Equals(this.Cdr, other.Cdr);
}
public override int GetHashCode() { return EqualityComparer<T>.Default.GetHashCode(this.Car) ^ (37 * EqualityComparer<ConsPair<T>>.Default.GetHashCode(this.Cdr)); }
}
public struct Reduction
{
public Reduction(string symbol, ConsPair<Reduction> stack, int offset)
{
this.Symbol = symbol;
this.Stack = stack;
this.Offset = offset;
}
public string Symbol;
public ConsPair<Reduction> Stack;
public int Offset;
public override string ToString() { return this.Stack != null ? string.Format("(\"{0}\", {1})", this.Symbol, this.Stack) : string.Format("\"{0}\"", this.Symbol); }
}
public static class Program
{
public static bool IsTerminal(string s) { return s.Length == 0 || s == "$" || s == "*" || s == ":" || s == ";" || s.Length > 0 && (char.IsUpper(s, 0) || s.StartsWith("_")); }
public static ConsPair<T> Cons<T>(T value, ConsPair<T> pair) { return new ConsPair<T>(value, pair); }
public static ConsPair<T> Cons<T>(T value) { return Cons(value, null); }
public static IDictionary<Item, IList<Item>> Closure(IList<Production> rules, Item item, IDictionary<Item, IList<Item>> result)
{
if (result == null) { result = new Dictionary<Item, IList<Item>>(); }
if (!result.ContainsKey(item)) { result[item] = new List<Item>(); }
for (int i = 0; i < rules.Count; i++)
{
var rule = rules[item.Rule];
if (rule.Count() > 0 && (item.Symbol == rule.Count() || rules[i].Symbol == rule[item.Symbol]))
{
var child = new Item(i, 0, null);
bool process = !result.ContainsKey(child);
if (process) { result[child] = new List<Item>(); }
result[child].Add(item);
if (process) { Closure(rules, child, result); }
}
}
return result;
}
public static IEnumerable<Reduction> ParseAscentDescent(IList<Production> rules, IList<string> input, int offset, Item item, ConsPair<Reduction> stack)
{
if (item.Symbol == rules[item.Rule].Count())
{
var n = rules[item.Rule].Count();
yield return new Reduction(rules[item.Rule].Symbol, n > 0 ? stack.Take(n).Reversed() : null, offset);
}
else if (IsTerminal(rules[item.Rule][item.Symbol]))
{
if (input[offset] == rules[item.Rule][item.Symbol])
{
foreach (var reduction in ParseAscentDescent(rules, input, offset + 1, new Item(item.Rule, item.Symbol + 1, item.Lookahead), Cons(new Reduction(rules[item.Rule][item.Symbol], null, offset), stack)))
{ yield return reduction; }
}
}
else
{
Debug.Assert(item.Symbol > rules[item.Rule].Count());
var closure = Closure(rules, item, null);
var reductions = new Queue<KeyValuePair<Item, Reduction>>();
foreach (var subItem in closure.Keys)
{
if (!subItem.Equals(item) && (rules[subItem.Rule].Count() == 0 || IsTerminal(rules[subItem.Rule][0])))
{
foreach (var reduction in ParseAscentDescent(rules, input, offset, subItem, null))
{
foreach (var parent in closure[subItem])
{
if (parent.Equals(item))
{
foreach (var result in ParseAscentDescent(rules, input, reduction.Offset, parent.Next(), Cons(reduction, stack)))
{ yield return result; }
}
reductions.Enqueue(new KeyValuePair<Item, Reduction>(parent, reduction));
}
}
}
}
while (reductions.Count > 0)
{
var pair = reductions.Dequeue();
foreach (var parent in closure[pair.Key])
{
var next = pair.Key.Next();
foreach (var reduction in ParseAscentDescent(rules, input, pair.Value.Offset, next, Cons(pair.Value, stack)))
{
if (parent.Equals(item))
{
foreach (var result in ParseAscentDescent(rules, input, reduction.Offset, parent.Next(), Cons(reduction, stack)))
{ yield return result; }
}
reductions.Enqueue(new KeyValuePair<Item, Reduction>(parent, reduction));
}
}
}
}
}
static void Main()
{
var start = Environment.TickCount;
var grammar = new Dictionary<string, IEnumerable<IList<string>>>()
{
{ "^", new[] { new[] { "rules", "$" } } },
{ "rules", new[] { new string[] { }, new[] { "rules", "rule" } } },
{ "rule", new[] { new[] { "LEXID", "COLON", "REGEX", "SEMICOLON" }, new[] { "SYNID", "COLON", "symbol", "SEMICOLON" } } },
{ "symbol", new[] { new[] { "symbol0" }, new[] { "symbol", "symbol0" } } },
{ "symbol0", new[] { new[] { "LEXID" }, new[] { "SYNID" } } },
{ "*", new[] { new[] { @"\s+" } } },
{ "COLON", new[] { new[] { ":" } } },
{ "LEXID", new[] { new[] { @"[A-Z_][A-Z_0-9]*|[*]|[\^]" } } },
{ "REGEX", new[] { new[] { @"\`(?:[^\\\`]|\\.)*\`" } } },
{ "SEMICOLON", new[] { new[] { ";" } } },
{ "SYNID", new[] { new[] { "[a-z][a-z_0-9]*" } } },
}.SelectMany(s => s.Value.Select(t => new Production(s.Key, t))).ToList();
for (int i = 0; i < grammar.Count; i++)
{
Console.WriteLine("{0}: {1}", i, grammar[i]);
}
var reductions = ParseAscentDescent(grammar, Enumerable.Repeat(new[] { "SYNID", "COLON", "SYNID", "SEMICOLON" }, 1).SelectMany(a => a).Concat(new[] { "$" }).ToArray(), 0, new Item(), null);
int count = 0;
foreach (var production in reductions)
{
Console.WriteLine(production);
count++;
}
Console.WriteLine("{0} parse tree(s).", count);
Console.WriteLine(Environment.TickCount - start);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Something went wrong with that request. Please try again.