2009-01-04

Verilogパーサで抽象構文木を生成するようにした

dev haskell verilog

Verilogファイルから、抽象構文木を生成できるようにしました。
処理できる構文はまだまだ限定的ですが。。

Haskell Parsecで直接扱うことのできない左再帰の構文を
右再帰に変形している部分があるのですが (expression構文のところ)
ここをパースして右再帰に変形前の構造に戻して構文木を作る処理で
ちょっと頭がこんがらがりそうでしたが（こんがらがりました）。
（左再帰のところは、chainlとか chainl1をうまく使えばよいのかな？？）

このブログを書いてる時点のソースコード
 http://github.com/kei-os/vparsec/tree/ccd8e9ceea5794b7b64acc366725bd967f61aa08

データコンストラクタとかデータ型の名前に迷いがあったり
多相的な型を使えばパーサをもっと簡潔に書けるんじゃない？とか
いろいろ思うところはありますが、とにかく
Haskell慣れしながら改善していきたいと思います。

いまのところ、生成した抽象構文木を printで出力するしか
確認する方法を用意できていませんが
今後は、確認しやすい形式でダンプする仕組みを用意できればと思っています。
また、モジュールのインスタンス化など、モジュールの階層構造を
うまく表してみたいと思っています。
（あと、やっぱりこまめにブログに書いていこうかと思います。
　それとスピードが必要＞＜）

とりあえず、実装したものをいくつかと、パース実行結果を記載しておきます。

代数的データ型 (ソースから抜粋)
パース実行関数 (ソースから抜粋)
ghci実行例 (実行ログ)

2009-01-03

今年は「射撃しながら前進」

dev book

前から読もうと思っていながら読めてなかった「Joel on Software」を読んでる。
射撃しながら前進〜！！
これだ。

Joel on Software

作者: Joel Spolsky,青木靖
出版社/メーカー: オーム社
発売日: 2005/12/01
メディア: 単行本
購入: 18人クリック: 371回
この商品を含むブログ (451件) を見る

2008-12-31

2008年の振り返り

misc

2008年も最後の日になったということで
来年の自分のためにも、今年一年を振り返っておきたいと思います。
ことしは四半期ごとのまとめがやりやすいらしい。

Q1 (1〜3月) - ネタ探し期

去年の秋頃から
「カイシャの中だけで力を発揮するのではなくて、一個人のエンジニアとしてアイデンティティを確立したい」
みたいな気持ちが強くなってきていたのですが
それで、「カイシャとぶつからない領域で何ができるか？」みたいな
自分探しというか、ネタ探し中心の時期でした。
そういうわけで、自分の心が何に反応するかみてみようと
いろいろと自分に刺激を与えていたようです。

で、なんかコンパイラに興味を持つようになって yacc/lexの勉強を始めたり
 小さな言語を作ってカイシャの仕事に適用したりして
コンパイラの雰囲気をつかんだりしていました。

Q2 (4〜6月) - 変化期

4月には今年一番のショックでもあり変化の材料でもあった
PowerBook G4が盗まれる出来事がありました。
もろもろのデータが失われたのは痛かったですが（とっても＞＜）
これを機に MacBookProを新調し、開発環境は快適になっていきました。

データを失ったのを教訓に、とにかくメモをいろいろとブログに残すようになりました。
それで、Vimperatorを使い始めたのをきっかけにヘルプを日本語に訳したエントリーを書いたら
このブログで今年最多アクセスのエントリーになってしまいました。
Vimperatorのヘルプを日本語にしてみたよ - kei-os2007 against the machine!!
いやいや、ほんとテキトーに書いてたので申し訳ないんですが...直すのもアレだったので。

この時期は Linuxデバドラの勉強してました。
YLUGのことを知ったのもこの時期。
それから Twitter始めました。
6月くらいからは、ブログを書く頻度を下げたかわりに
メモ書き中心だった内容を、人に読んでもらうのを意識しながら書くようになってきて
行動が外向きに変化してきたように思います。

Q3 (7〜9月) - 出撃期

イベントやこれまで参加したことのなかった勉強会に足を運んだ時期でした。
第1回 VimM勉強会に参加して LTできたのは良い経験でした。

あと、ブログに書いてるのはこんな感じ。

勉強会の内容だけでなく、いろいろな人に会ってお話して
人とのつながりができたのが収穫でした。
そして、もう孤独じゃないんだ、と。

Q4 (10〜12月) - 開発期

土日は子守りで家にいることが多かったので、イベントに出かけられず
少し歯がゆい状態でしたが、夏頃から Haskellの勉強していたのを
具体的な成果物につなげるべく、Haskell Parsecライブラリを使って Verilogパーサを書き始めました。
githubのリポジトリを活用した開発サイクルが身についてきました。
(いまのソースコード)

というわけでまとめると

カイシャの枠組みでのエンジニア活動だけでなく、個人として動き始めることができた年でしたが
まだスピードが足りないなぁ、と思うし、思い切りも足りないなぁ、と思います。
もっとフットワークを軽くして、来年は小さなアウトプットをたくさん出して
小さく繋いでいくようなやり方を意識する必要があるかもしれないです。

今年 1年間、kei-os2007 against the machine!! に来てくださった皆様
どうもありがとうございました。
あまりブログには書いていませんが、読んでもらえているということが、とても励みになっています。
来年は、このブログを通じて何かお返しできればいいな、と思います。

とりあえず、年明けからはまた週末のイベントには参加できそうです。
（子守り強調月間もおわったので）
2009年、走ろう！

来年もどーぞよろしくです！

追記

「最多アクセス数」といっているのは、google analyticsで見た結果です。
下図のアクセス数のグラフは「週ごと」で出しています。
PVの上位5つが出てますが、Vimperatorのエントリーへのアクセスが最多なんですね。

2008-12-13

抽象構文木をどうしようかと

dev haskell verilog

とりあえず Verilogのシンタックスチェックできる程度、ということで
（意味解析してないから、たとえば入力ポートの信号と input宣言の信号が合ってなくても文句言わないくらいザルですし）
遠くを見ると気を失いそうになるのですが
わからないことを書き出して気持ちを楽にしながら進んでいくとします。
いや、ほんとわからないことだらけだなぁ。
でも Haskell Parsecとは仲良くなれてきたはず。

で、抽象構文木を作らなきゃ、ということで考えているのですが
ただ考えてもわからないと思うので、先人の知恵を拝借しようと

Icarus Verilogの実装をみたりしています。
http://sourceforge.net/projects/iverilog

あと、Ruby Hacking Guide (RHG)を読んだり、とか。
http://i.loveruby.net/ja/rhg/

それから「スクリプトエンジンプログラミング」の本を読んだり実装を見たり、とか。

スクリプトエンジンプログラミング

作者: 坂本千尋
出版社/メーカー: SBクリエイティブ
発売日: 2008/09/27
メディア: 単行本
購入: 6人クリック: 248回
この商品を含むブログ (28件) を見る

まずはモジュールの構造を抽出したいと思っているのだけど
完全並列に実行するために必要な要素を、データ構造に仕込んでおきたいなぁ、とか考えたりすると
Icarus Verilogの実装が参考になるかな、と。
ツリー構造というかグラフ構造を意識しないといけないかなぁ、とか考えたり。

Haskellも Parsecじゃない部分（ふつうに Haskellな部分）と
仲良くなっていかないとなぁ。

ブログは頻繁には更新できていませんが、githubにはちまちまと更新しています。
もし気にしてくださってる方がいらっしゃいましたら
githubの方をウォッチしてみていただければ、と思います。
http://github.com/kei-os/vparsec/tree/master

あ、そうか、githubに Wikiつくったほうがいいな。

2008-12-03

左再帰の除去についてプチまとめ

dev haskell verilog

Verilogパーサを書き進めていくと、Verilog構文の左再帰に遭遇します。
Haskell Parsecは再帰下降パーサということで、左再帰の構文をそのまま書くと
stack overflowを起こしてうまく処理を続けられません。
うまいこと左再帰を除去（右再帰に置き換える）する必要があります。
というわけで、ドラゴンブックを読んで仕入れた知識をもとに
うまいこと左再帰を除去してみたので、書いておきます。

左再帰の文法が

    A → Aα | β

のようにあるとき、↓のように置き換えていきます。

    A  → βA'
    A' → αA' | ε

とゆーわけで、Verilogの BNFから、左再帰の部分を抜粋してみます。

<expression>
    ::= <primary>
    ||= <UNARY_OPERATOR> <primary>
    ||= <expression> <BINARY_OPERATOR> <expression>
    ||= <expression> <QUESTION_MARK> <expression> : <expression>
    ||= <STRING>

んー、このままだと、ちょっとわかりにくいので、変形してみます。
とりあえず A, α, βと対応させられるように、ということで。

変形その1

<expression>
    ::= <Beta>
    ||= <expression> <BINARY_OPERATOR> <expression>
    ||= <expression> <QUESTION_MARK> <expression> : <expression>

<Beta>
    ::= <primary>
    ||= <UNARY_OPERATOR> <primary>
    ||= <STRING>

構造が単純になってきました。
が、もうちょっと変形します。

変形その2

<expression>
    ::= <Beta>
    ||= <expression> <Alpha1>
    ||= <expression> <Alpha2>

<Alpha1>
    ::= <BINARY_OPERATOR> <expression>

<Alpha2>
    ::= <QUESTION_MARK> <expression> : <expression>

<Beta>
    ::= <primary>
    ||= <UNARY_OPERATOR> <primary>
    ||= <STRING>

単純な左再帰の文法にしか見えなくなりました。（見えなくなったはず！）

そういうわけで、この文法を右再帰の文法に変形すれば完了、と思います。

変形その3

<expression>
    ::= <Beta> <expression_>
    ||= <Beta> <expression__>

<expression_>
    ::= [<BINARY_OPERATOR> <expression> <expression_>]

<expression__>
    ::= [<QUESTION_MARK> <expression> : <expression> <expression__>]

<Beta>
    ::= <primary>
    ||= <UNARY_OPERATOR> <primary>
    ||= <STRING>

（たぶんこれでよいのではないかなぁ？）

Haskellコード

じゃ、この部分の Haskellコードです。
ソース全体は githubにて。まだまだまだまだ書きかけですが＞＜
http://github.com/kei-os/vparsec/tree/master/Vparsec.hs

lexeme, tryを入れすぎな気もします。
まだまだ Haskell経験が浅いな。

expression :: Parser String
expression = do { a <- optExpression
                ; b <- expression_ <|> expression__
                ; return $ a ++ b }
        <?> "expression"
    where
        optExpression = try(primary)
          <|> try(do { a <- lexeme unaryOperator
                     ; b <- lexeme primary
                     ; return $ a ++ b })
          <|> string'
        expression_
            = try(do { a <- lexeme binaryOperator
                     ; b <- lexeme expression
                     ; c <- lexeme expression_
                     ; return $ a ++ b ++ c })
          <|> string ""
        expression__
            = try(do { a <- lexeme questionMark
                     ; b <- lexeme expression
                     ; c <- colon
                     ; d <- lexeme expression
                     ; e <- lexeme expression__
                     ; return $ a ++ b ++ c ++ d ++ e })
          <|> string ""

2008-11-26

lexemeパーサを使うようにした

dev haskell verilog

今週にはいって風邪をひいたりして、あまり作業を進められていないのですが
とはいえ、溜め込むと書くのが億劫になってしまうので、少しでも書いておこうと思います。

前回、とりあえず Vparsecという名前で書いています - kei-os2007 against the machine!! という内容で
Verilogパーサを書き始めましたが、空白の読み飛ばしとかもパース処理の中で実行していて
パース処理が無駄に煩雑になってしまっていました。
そこで、Parsecの Tokenライブラリと呼べばよいのでしょうか、
これを importして、不要な空白を読み飛ばす lexemeパーサを活用し
パーサ記述の煩雑さを減らしてみました。

今回の lexemeパーサの追加にあたって、下のような記述を加えています。

import qualified Text.ParserCombinators.Parsec.Token as P
import Text.ParserCombinators.Parsec.Language

-- XXX Mmm... TODO
verilogStyle =  emptyDef
            { commentStart = ""
            , commentEnd = ""
            , commentLine = ""
            , nestedComments = False
            , identStart = letter <|> char '_'
            , identLetter = alphaNum <|> oneOf "_'"
            , opStart = opLetter emptyDef
            , opLetter = oneOf ":!#$%&*+./<=>?@\\^|-~"
            , reservedOpNames = []
            , reservedNames = []
            , caseSensitive = True
            }

lexer = P.makeTokenParser(verilogStyle)

reserved    = P.reserved lexer
operator    = P.operator lexer
reservedOp  = P.reservedOp lexer

natural     = P.natural lexer

symbol      = P.symbol lexer
lexeme      = P.lexeme lexer
whiteSpace  = P.whiteSpace lexer

parens      = P.parens lexer
braces      = P.braces lexer
angles      = P.angles lexer
brackets    = P.brackets lexer

semi        = P.semi lexer
comma       = P.comma lexer
colon       = P.colon lexer
dot         = P.dot lexer

semiSep     = P.semiSep lexer
semiSep1    = P.semiSep1 lexer
commaSep    = P.commaSep lexer
commaSep1   = P.commaSep1 lexer

import qualified 〜を使うことによって
Text.ParserCombinators.Parsec.Tokenを P で置き換えて書けるようにしています。
記述量の節約ですね。

verilogStyleは、いまのところ、とりあえずの形だけです。すいません。
（今後、作り込んでいきたいと思っています。）

で、makeTokenParserを使って、トークンパーサを生成しています。lexerです。
この lexerを使って、新しく lexemeパーサを定義しています。
（reservedから commaSep1の行まで）

というわけで、lexemeパーサに置き換え後のソースコードを貼っておきます。
spaceや spacesによる読み飛ばし処理がなくなっています。
そのかわりに、新たに導入した symbol, lexeme, whiteSpace, parens, braces, semi, comma, colon, dot といったパーサが登場しています。

あと、細かなことですが func = do {a <- hoge; return a} のように書いてあった箇所は
func = hoge の記述に変えました。

次は、semantic valueのことを考えて、プリプロセス処理のことを考えて、と
進んでいくものと思われます。