X-Mozilla-Status: 0001 X-Mozilla-Status2: 00000000 Delivered-To: barryleiba.mailing.lists@gmail.com Received: by 10.58.170.71 with SMTP id ak7csp69977vec; Sun, 3 Nov 2013 19:20:47 -0800 (PST) X-Received: by 10.68.234.165 with SMTP id uf5mr15646665pbc.41.1383535247274; Sun, 03 Nov 2013 19:20:47 -0800 (PST) Return-Path: Received: from mail.ietf.org (mail.ietf.org. [2001:1890:123a::1:1e]) by mx.google.com with ESMTP id ba2si8702949pbc.208.2013.11.03.19.20.46 for ; Sun, 03 Nov 2013 19:20:47 -0800 (PST) Received-SPF: pass (google.com: domain of abnf-discuss-bounces@ietf.org designates 2001:1890:123a::1:1e as permitted sender) client-ip=2001:1890:123a::1:1e; Authentication-Results: mx.google.com; spf=pass (google.com: domain of abnf-discuss-bounces@ietf.org designates 2001:1890:123a::1:1e as permitted sender) smtp.mail=abnf-discuss-bounces@ietf.org; dkim=pass header.i=@ietf.org Received: from ietfa.amsl.com (localhost [IPv6:::1]) by ietfa.amsl.com (Postfix) with ESMTP id 239F511E828E; Sun, 3 Nov 2013 19:20:46 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=ietf.org; s=ietf1; t=1383535246; bh=8xcF2Y3CnTSKtmD4aVHFNG7lv2q5ZMRkDIRZw+Sjj/I=; h=From:To:Date:Message-ID:References:In-Reply-To:MIME-Version:Cc: Subject:List-Id:List-Unsubscribe:List-Archive:List-Post:List-Help: List-Subscribe:Content-Type:Content-Transfer-Encoding:Sender; b=hFH81n48LV2oLaTrMVevph6SNx7VukMrTJWCqm7hn3Em+UEITNA76LQvrnLJSKjwO pYdWxsePMIe4a7eFcRG7YdAwJIuNuoZGnoFlxKv8aWl/W/irH9Uq6yDCR+HzTR3cdy nUZdcT/R2fyrTHyG3a1Rua51BfnJ3uRTcTgG2FgI= X-Original-To: abnf-discuss@ietfa.amsl.com Delivered-To: abnf-discuss@ietfa.amsl.com Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 7290911E828C for ; Sun, 3 Nov 2013 19:20:44 -0800 (PST) X-Virus-Scanned: amavisd-new at amsl.com X-Spam-Flag: NO X-Spam-Score: -2.712 X-Spam-Level: X-Spam-Status: No, score=-2.712 tagged_above=-999 required=5 tests=[AWL=-0.113, BAYES_00=-2.599] Received: from mail.ietf.org ([12.22.58.30]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id pXokxqnY-i0c for ; Sun, 3 Nov 2013 19:20:40 -0800 (PST) Received: from mout.gmx.net (mout.gmx.net [212.227.15.19]) by ietfa.amsl.com (Postfix) with ESMTP id 4890211E828A for ; Sun, 3 Nov 2013 19:20:39 -0800 (PST) Received: from netb.Speedport_W_700V ([91.35.51.144]) by mail.gmx.com (mrgmx103) with ESMTPA (Nemesis) id 0LbdiB-1W57ks1oGB-00lE1x for ; Mon, 04 Nov 2013 04:20:37 +0100 From: Bjoern Hoehrmann To: Bjoern Hoehrmann Date: Mon, 04 Nov 2013 04:20:37 +0100 Message-ID: References: <52717320.4000704@nostrum.com> <52733E23.2050103@alvestrand.no> In-Reply-To: X-Mailer: Forte Agent 3.3/32.846 MIME-Version: 1.0 X-Provags-ID: V03:K0:QcDbFvs8COb8gzqsSpDpJHV5wapx/CLPtv3ua6p8SoxJ6zjUnWf 6cFCNuoo0FvvWQrZRcIvil35SBZZpqhBnvutmQaTBd9sXLDGBixYwKniq1Jp/iblWPfcv/y keufruSkQxES67hopcvBIS6qnEUbb5/mWKykrY3hmjJkIxu4WMA0Xs0usR2FG8Y7uwdseYg VRjZHOXzVk7VwYqSuZglg== Cc: Martin Thomson , abnf-discuss@ietf.org Subject: Re: [abnf-discuss] addIceCandidate behavior X-BeenThere: abnf-discuss@ietf.org X-Mailman-Version: 2.1.12 Precedence: list List-Id: "General discussion about tools, activities and capabilities involving the ABNF meta-language" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: quoted-printable Sender: abnf-discuss-bounces@ietf.org Errors-To: abnf-discuss-bounces@ietf.org * Bjoern Hoehrmann wrote: >My tools have the same problem and I was hoping for inspiration. Last >few times I searched I had little luck in finding a proper description >of possible conversion processes. Perhaps the problem was that I looked >mainly for grammar rewriting techniques, preserving as much of the in- >put grammar as possible, rather than creating an FSA from the grammar, >and then turning the FSA into a regex. https://gist.github.com/hoehrmann/7297242 is a quick and dirty Perl script that turns an ABNF grammar into a hopefully equivalent ABNF grammar is essentially in Greibach Normal Form plus extra rules for keeping intact which rules match the empty string (for all rules, not just a selected start rule). Importantly that means there is no left recursion. It does not use the choice operator other than as `=3D/` and normalises all terminal-like constructs into sequences of the form `%x0000-10FFFF` and does not use line folding or any other feature, it expands repetitions, no comments, and so on. There are various relatively simple ways to go from there to an NFA or a regular expression or a DFA for the regular rules in it. I did not really test it much so far, I am sure there are bugs lurking, but it gives a reasonable idea of what is involved and might be useful for comparison purposes. It is unfortunate that implementations of all the standard algorithms in this area are hard to come by... -- = Bj=F6rn H=F6hrmann =B7 mailto:bjoern@hoehrmann.de =B7 http://bjoern.hoehrma= nn.de Am Badedeich 7 =B7 Telefon: +49(0)160/4415681 =B7 http://www.bjoernsworld.de 25899 Dageb=FCll =B7 PGP Pub. KeyID: 0xA4357E78 =B7 http://www.websitedev.d= e/ = _______________________________________________ abnf-discuss mailing list abnf-discuss@ietf.org https://www.ietf.org/mailman/listinfo/abnf-discuss