From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: Stefan Israelsson Tampe Newsgroups: gmane.lisp.guile.user Subject: Operator parser in guile-log Date: Sun, 18 Aug 2013 23:06:12 +0200 Message-ID: <2682233.8KlgUH4fnh@warperdoze> NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: 7Bit X-Trace: ger.gmane.org 1376860004 28567 80.91.229.3 (18 Aug 2013 21:06:44 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Sun, 18 Aug 2013 21:06:44 +0000 (UTC) To: guile-user@gnu.org Original-X-From: guile-user-bounces+guile-user=m.gmane.org@gnu.org Sun Aug 18 23:06:46 2013 Return-path: Envelope-to: guile-user@m.gmane.org Original-Received: from lists.gnu.org ([208.118.235.17]) by plane.gmane.org with esmtp (Exim 4.69) (envelope-from ) id 1VBABS-0002u0-6v for guile-user@m.gmane.org; Sun, 18 Aug 2013 23:06:46 +0200 Original-Received: from localhost ([::1]:40027 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1VBABR-00070x-Im for guile-user@m.gmane.org; Sun, 18 Aug 2013 17:06:45 -0400 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:37147) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1VBABA-00070i-VI for guile-user@gnu.org; Sun, 18 Aug 2013 17:06:37 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1VBAB2-0002kj-Gk for guile-user@gnu.org; Sun, 18 Aug 2013 17:06:28 -0400 Original-Received: from mail-la0-x22a.google.com ([2a00:1450:4010:c03::22a]:53252) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1VBAB2-0002ka-4m for guile-user@gnu.org; Sun, 18 Aug 2013 17:06:20 -0400 Original-Received: by mail-la0-f42.google.com with SMTP id ep20so2896898lab.1 for ; Sun, 18 Aug 2013 14:06:18 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=from:to:subject:date:message-id:user-agent:mime-version :content-transfer-encoding:content-type; bh=rtlHgU3bOeOaxRBqEMhHFPq57lyKNtfeENefNURJmEk=; b=GjhROKvi8++XY7ZYdK8YbAdNOQeVGMZsUYpLQe7HoOGUIEx6ORkORLhGxFEsOLtrko poNip+kCxAkIAOJHdD1PLQohlKRUxU/LbLgJcHiE8DZnpvuB2wYwEFBrCREJwSWi/por bHJYuZYlYoTPEP+5ouPUpx98RtseM+LkiIvKj8iWhtPWvNMnd0o1GDkrFvYzc8TF/eEE eEI+tlywsfs83XaySdezZsfbeEskBcn/NIitGOwkEBE568/+O9thN7zHNBU/36pgr3ha Er1TLYFgKps7mG5j6DlrnrlAyThiOsyC6zcusFIguc5Y8eUd7SeylH3E1x29vVjqMgn5 ZA9A== X-Received: by 10.112.198.39 with SMTP id iz7mr8486891lbc.24.1376859978794; Sun, 18 Aug 2013 14:06:18 -0700 (PDT) Original-Received: from warperdoze.localnet (1-1-1-39a.veo.vs.bostream.se. [82.182.254.46]) by mx.google.com with ESMTPSA id n15sm3336814laa.2.1969.12.31.16.00.00 (version=TLSv1.1 cipher=ECDHE-RSA-RC4-SHA bits=128/128); Sun, 18 Aug 2013 14:06:17 -0700 (PDT) User-Agent: KMail/4.9.5 (Linux/3.5.0-30-generic; KDE/4.9.5; x86_64; ; ) X-detected-operating-system: by eggs.gnu.org: Error: Malformed IPv6 address (bad octet value). X-Received-From: 2a00:1450:4010:c03::22a X-BeenThere: guile-user@gnu.org X-Mailman-Version: 2.1.14 Precedence: list List-Id: General Guile related discussions List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: guile-user-bounces+guile-user=m.gmane.org@gnu.org Original-Sender: guile-user-bounces+guile-user=m.gmane.org@gnu.org Xref: news.gmane.org gmane.lisp.guile.user:10645 Archived-At: Hi all, One of the peculiarities of prolog is it's ability to redefine it's parsing operators. prolog code is really basically one expression and a configurable operator parser id let loose on it. In a paper referenced in previous mail they describe the parser implemented in prolog and I ported and tested it just now on guile-log. It's a fun exercise and it helps in understanding how well the guile-log framework work. So, to show it off, let's construct a little calculator parser. The operators are in precedence groups postfix application "(expr)" prefix - binary * binary / binary + binary - binary = binary , atoms are: C-identifiers and integers. The requisite to make it work is the following, (use-modules (ice-9 match)) (use-modules (ice-9 pretty-print)) (use-modules (logic guile-log)) (use-modules (logic guile-log parser)) (use-modules (logic guile-log parsing operator-parser)) We will use p-term as the expression matcher, it will be bound later, also an application is '(' expr ')' or '(' p-term ')' now a matcher operator will need a prefix to work and a matcher to implement advanced matcher operators, '(' is the prefix we will enter later, so (define p-term #f) (define application (s-and! (s-seq p-term (s-char #\))))) No we define the operator table, (define ops (make-opdata)) (add-operator ops 'xfy "," 6 s-ws*) (add-operator ops 'xfy '= 5 s-ws*) (add-operator ops 'xfy '+ 4 s-ws*) (add-operator ops 'xfy '- 4 s-ws*) (add-operator ops 'xfy '/ 3 s-ws*) (add-operator ops 'xfy '* 3 s-ws*) (add-operator ops 'fy '- 2 s-ws*) (add-operator ops 'yf "(" 1 application) To note here ise 0) ,(6) us the loosest bound operator and application(1) the tightest bounded operator 1) s-ws* and 'application' is what will be matched after the prefix s-ws* is just possible whitespace removal 2) xfy = lr binary operator, fy is prefix and yf is postfix also note that the matching head pattern for the operator is added. Over to designing the atoms and produce the expression matcher, (define op-match (letrec ( ;; numbers (num-token (s-seq s-ws* (mk-simple-token #:number (s+ (s-reg! "[0-9]"))) s-ws*)) ;; C identifiers (id-tok (s-seq s-ws* (mk-simple-token #:identifier (s-seq (s-reg! "[_a-zA-Z]") (s* (s-reg! "[_a-zA-Z0-9]")))) s-ws*)) ;; subexpresions in paranthesis (par-token (s-seq (s-char #\() s-term (s-char #\)))) ;; And the actual atom (atom (s-or (s-and! par-token) (s-and! id-tok) (s-and! num-token))) ;; The raw output operator term (term (mk-operator-expression atom ops)) ;; Make it more convinient to use (s-term (s-seq s-ws* ( (c) (.. (term end-level))) s-ws*)) ;; the returned matcher will make sure to match the end (op-match (s-seq s-term s-eof))) (set! p-term s-term) ;; set the p-term (used in the added operator) op-match)) So op-match will be the thing to match for, The output is not as nice yet, let's make it nicer, (define (show x) (match x ((#:identifier a) (string->symbol a)) ((#:number n) (string->number n)) ((('yf _ "(" val) x . _) (list #:application (show x) (show val))) ((((or 'xfy 'yfx 'xfx) _ op . _) x y . _) `(,op ,(show x) ,(show y))) ((((or 'xf 'yf 'fx 'fy) _ op . _) x . _) `(,op ,(show x))) ((_ . _) (map show x)) (x x))) Write a run macro, (define (p-calc str) (let ((p (parse str op-match))) (pretty-print (show (car p))) (if #f #f))) And we can have a try, scheme@(guile-user) [10]> (p-calc "((b * 4 * c(2))+ (4 * a(1)))") (+ (* b (* 4 (#:application c 2))) (* 4 (#:application a 1))) scheme@(guile-user) [10]> (p-calc "((b * 4 + c(2))+ (4 - - a(1)))") (+ (+ (* b 4) (#:application c 2)) (- 4 (- (#:application a 1)))) scheme@(guile-user) [10]> (p-calc "(c = (b * 4 + c(2))+ (4 - - a(1)), a*b+c)") ("," (= c (+ (+ (* b 4) (#:application c 2)) (- 4 (- (#:application a 1))))) (+ (* a b) c)) There sill remain som buggs not shown here but this is a pretty good start. Have fun!