Lisp, Python, Perl, Ruby Code to Validate Matching Brackets

Xah Lee, 2011-07-21, 2011-07-23

This is a preliminary report on scripts of several languages to validate matching brackets.

Problem Description

Little Parser Problem Challenge: Matching Pairs Validation

The problem is to write a script that can check a dir of text files (and all subdirs) and reports if a file has any mismatched matching brackets.

• The files will be utf-8 encoded (unix style line ending).
• If a file has mismatched matching-pairs, the script will display the file name, and the line number and column number of the first or last instance where a mismatched bracket occures. (or, just the char position (as in emacs's “point”)) Exactly which position is considered as the “first” or “last” doesn't matter much, as long as it report a char that breaks the nesting matching pair syntax.
• The matching pairs are all single Unicode chars. They are these and nothing else: () {} [] “” ‹› «» 【】 〈〉 《》 「」 『』 . Note that ‘single curly quote’ is not consider matching pair here.
• You script must be standalone. Must not be using some parser tools. But can call lib that's part of standard distribution in your lang.

Here's a example of mismatched bracket: ([)], (“[”), ((, 】 etc. (and yes, the brackets may be nested. There are usually text between these chars.)

I'll be writing a emacs lisp solution and post in 2 days. Ι welcome other lang implementations. In particular, perl, python, php, ruby, tcl, lua, Haskell, Ocaml. I'll also be able to eval common lisp (clisp) and Scheme lisp (scsh), Java. Other lang such as Clojure, Scala, C, C++, or any others, are all welcome, but i won't be able to eval it. JavaScript implementation will be very interesting too, but please indicate which and where to install the command line version.

I hope you'll find this a interesting “challenge”. This is a parsing problem. I haven't studied parsers except some Wikipedia reading, so my solution will probably be naive. I hope to see and learn from your solution too.

i hope you'll participate. Just post solution here. Thanks.

Solutions

Emacs Lisp

• validate_brackets_Xah_Lee.el

Detailed explanation at Emacs Lisp: Batch Script to Validate Matching Brackets.

Jon Snader (jcs) wrote 2 versions in elisp. See: Xah's Challenge (Part 2) 2011-07-21 By Jon Snader. @ irreal.org…. Ι haven't studied it yet.

Python

• validate_brackets_Raymond_Hettinger.py

This report is incomplete. So far Raymond Hettinger's python 3 code is the only working code other than elisp. None of the following works on my machine.

For the original post of this problem and the discussion, see: a little parsing challenge ☺ 2011-07-17 @ groups.google.com….

Thanks to the many who have written code and made helpful comments. I may come back to clean this up, in the coming weeks. If you can correct one of the following programs, please comment.

Pending Solutions

Python

• validate_brackets_Thomas_Jollans.py so far didn't work, possibly unix/Windows issues.
• validate_brackets_Billy_Mays.py doesn't do Unicode and doesn't report error position.
• validate_brackets_Thomas_Lahn.py doesn't seem to be correct. No report on bad file.

Ruby

• validate_brackets_Robert_Klemme.rb Requires ruby19, currently i have 1.8.7.
• validate_brackets_wj_wax.rb Incomplete. Doesn't read dir. Doesn't do Unicode.

Perl

• validate_brackets_Rouslan_Korneychuk_2.pl need test

Common Lisp

• validate_brackets_Madhu.lisp