home ホーム search 検索 -  login ログイン  | help ヘルプ

find 検索

901 - 910 / 1320    [|<]  [|<]  [<]  91  92  93  94  95  96  97  98  99  100   [>]  [>|][>|]
タイトル/名前 更新者 更新日
日記/2009/11/24/構文解析(LL,LR,LALR,yacc関連)メモ msakamoto-sf 2009-11-24 12:29:00
日記/2009/11/23/yaccの練習 msakamoto-sf 2009-11-23 20:41:44
日記/2009/11/22/"俺はSEをやめるぞ！ジョジョーッ！！" msakamoto-sf 2009-11-22 17:50:07
C言語系 msakamoto-sf 2009-11-21 01:54:10
技術/UNIX/diff msakamoto-sf 2009-11-20 17:18:13
技術/UNIX/patch msakamoto-sf 2009-11-20 17:18:02
技術/UNIX/cpio msakamoto-sf 2009-11-20 17:17:49
技術/UNIX/sharutilsのuuencode,uudecodeによるBASE64エンコード,デコード msakamoto-sf 2009-11-20 11:06:26
技術/UNIX/「UNIX用のGeekな小技10個」メモ msakamoto-sf 2009-11-20 11:05:53
C言語系/memos/gettext msakamoto-sf 2009-11-18 20:22:15
ソート項目 / ソート順     1ページ 件ずつ表示

日記/2009/11/24/構文解析(LL,LR,LALR,yacc関連)メモ  ↑

所有者: msakamoto-sf    作成日: 2009-11-24 11:35:42
カテゴリ:

ざっとまとめただけです。

大元：文脈自由文法

元々は言語学だが、プログラミング言語の文法や構文を扱うのに優れている。
で、入力されたテキストの文法的な関係を説明するのが構文解析。

構文解析は通常、字句解析結果をその言語の文法に沿った木構造に変換する。
日本語で言えば助詞、プログラミング言語では"("や"{"などの括弧など、グループ化の為の葉まで含めたのが構文木。
英語版だと"Concrete syntax tree"：http://en.wikipedia.org/wiki/Concrete_syntax_tree

構文木から、"("や"{"などプログラム的に意味のない部分を取り除いたのが抽象構文木。
英語版だと"Abstract syntax tree"：http://en.wikipedia.org/wiki/Abstract_syntax_tree

構文解析を行うのが構文解析器。
その例として、次の二種類。

  • トップダウン構文解析
    • 入力テキストを、入力された順番に解析して、生成規則を適用していく。
    • LL法がプログラミング言語で主流。左端導出を使う。
    • k個のトークンを先読みする場合はLL(k)法と呼ばれる。1990年代まではLL(1)までしか使われていなかったが、計算機の性能向上によりJavaCCやANTLRなどで1以上のkによるLL(k)法を使うパーサもあらわれた。
  • ボトムアップ構文解析
    • 入力テキストを、最後に入力された要素から逆順に解析して、生成規則を適用していく。
    • LR法がプログラミング言語で主流。右端導出を使う。
    • yaccなどは先読み(LookAhead)を行うLRである、LALR法を使っている。

左端導出、右端導出については「文脈自由文法」を参照。

トップダウン構文解析に使われる解析手法でもう一つ有名だったのが再帰下降構文解析。
LL法とどう違うかというと(Wikipediaからの抜き書きです)・・・

  • "バックアップ"の無い再帰下降は「予言的パーサ」とも呼ばれ、これはLL(k)文法でのみ実現可能。左再帰が含まれていると使えない。
  • "バックアップ"のある再帰下降はLL(k)以外の文法でも使えるが、時間かかるみたい。

基本的にLL(k)法を扱うパーサは再帰下降と考えてOKっぽい。

左再帰というのが出てくるが、これは生成規則の先頭に(=左側に)自分自身が再度定義されている規則。
右再帰というのは逆に、生成規則の後ろに(=右側に)自分自身が再度定義されている規則。 

左再帰:
A => A + B
右再帰:
A => B + A

詳細は以下参照：

yaccの内部動作を知りたい場合は、下記英語リソースが図や表も多用されてて分かりやすかった・・・ように見えるので、情けないけど「あとで見る」という事に。


プレーンテキスト形式でダウンロード
現在のバージョン : 1
更新者: msakamoto-sf
更新日: 2009-11-24 12:29:00
md5:0c9521934f1e6490711ec5e20c3bf7c9
sha1:67aca287c3178e90a639df06d18fff364bfdcb64

日記/2009/11/23/yaccの練習  ↑

所有者: msakamoto-sf    作成日: 2009-11-23 20:26:15
カテゴリ: プログラミング 

プログラミング言語を作る
勉強を始めたのだけれど、速攻でyaccとlexのところで躓いてしまいました。トークンがスタックにshiftされ(=積まれ)、条件にマッチするとreduce(=設定したイベントが走り一つ上位の非終端子にランクアップ)されるのは良いのだけれど、conflictの所が良く理解できないっす。

というわけで、同書の電卓プログラムをベースに単純なものから試行錯誤でグレードアップしていき、最終的に同書と同じレベルに戻してみるというすごい無駄な事をしてみました。。スミマセン、こういうやり方でないと上手く頭に入ってこないんです・・・。つくづく技術書の読み方というか勉強の仕方が下手くそだと思う今日この頃。

※CentOS 5.2 上の byacc-1.9, flex-2.5.4a で動作確認しています。特に "y.output" ファイルのフォーマットなどはバージョンにより異なる可能性がある為注意して下さい。

(全て表示する)
プレーンテキスト形式でダウンロード
現在のバージョン : 1
更新者: msakamoto-sf
更新日: 2009-11-23 20:41:44
md5:d3c88f1b50d4d5db7364a374b32b4580
sha1:789bbc9eeaa67ded6bd42d049b6eec2259ed618d

日記/2009/11/22/"俺はSEをやめるぞ！ジョジョーッ！！"  ↑

所有者: msakamoto-sf    作成日: 2009-11-22 17:40:07
カテゴリ:

やっぱりサーバコンソールでキーボードをタイピングし続ける方が楽しくてたまらないんだよぉぉーーーーーーーー！！

いや、嘘かも。スミマセン。少し復活してきた。

ちなみに、高校～大学～社会人と人生を支えてきてくれた小野不由美の十二国記シリーズを昨日手放しました。作品が嫌いになったわけではなくて、自分の中で役目が終わったと思ったからです。今までありがとう。
これからの人生は、ひろさちやベースの仏教観を体の良い言い訳に活用して乗り切りたいと思います。


プレーンテキスト形式でダウンロード
現在のバージョン : 1
更新者: msakamoto-sf
更新日: 2009-11-22 17:50:07
md5:dbb234dd8e03f514d5a3709c45a707b9
sha1:cc11dba9df10cfca41c108dc04e2356e5136ecc1

C言語系  ↑

所有者: msakamoto-sf    作成日: 2009-11-16 09:55:01
カテゴリ: C言語 

技術 の方に結構C言語とかLinux/UNIXとかごちゃまぜに置いてありますが、こちらは
「C/C++を中心とし、UNIX/Linux上の開発ツール話その他」
となります。場合によってはWindows上のC/C++と開発ツール話も出てくるかも知れません。


プレーンテキスト形式でダウンロード
現在のバージョン : 2
更新者: msakamoto-sf
更新日: 2009-11-21 01:54:10
md5:65fa6ad23b37e96419ff59088381c438
sha1:8904643e31a083284eb17bb52bdc7b5cb4c62f92

技術/UNIX/diff  ↑

所有者: msakamoto-sf    作成日: 2009-11-19 14:19:30
カテゴリ: Linux UNIX シェルスクリプト 

細かいところとかが結構「あれれ？」となりやすいので、diffの使い方を今一度自分用にメモ。

なお、normal/context("-c")/unified("-u")の3種類は、上記Linux/FreeBSD/Solaris10の各diffでサポートされている。
Solaris10のdiffのみ、新ファイルに関連する"-N"オプションが記述されていない。

(全て表示する)
プレーンテキスト形式でダウンロード
現在のバージョン : 1
更新者: msakamoto-sf
更新日: 2009-11-20 17:18:13
md5:877f2e059ae2d6d57f9675c5523db005
sha1:2c3abcf165ad798b30865eb120964586165cd2fa

技術/UNIX/patch  ↑

所有者: msakamoto-sf    作成日: 2009-11-19 16:00:31
カテゴリ: Linux UNIX シェルスクリプト 

細かいところとかが結構「あれれ？」となりやすいので、patchの使い方を今一度自分用にメモ。

基本

patchコマンドはカレントディレクトリのソースツリーに対して処理する。 

patch < patchfile

# タブやスペースマッチの条件を緩めにする
patch -l < patchfile

# パッチ適用ファイルに対して".orig"拡張子をつけてバックアップする。
patch -b < patchfile

"-b"によるバックアップファイルの拡張子を変更するには・・・ 

GNUの場合：
patch -b -z .bk < patchfile
FreeBSDの場合：
patch -b .bk < patchfile

"-d ディレクトリ名"を指定すると、そのディレクトリに移動してから処理が始まる。

(個人的に)一番重要なオプション "-pNum" + "--dry-run"/"-C or --check"

patchを実行する前に、「何が行われるのか確認だけしたい」場合は以下のオプションを使う。 

GNUの場合：
patch ... --dry-run ... < patchfile
FreeBSDの場合：(-C or --check)
patch ... -C ... < patchfile

patchを実行する時に個人的に極めて重要だと考えているオプションが "-pNum" オプションである。
"-pNum"を使うと、patchfileで見つかったファイル名それぞれについてNum個のスラッシュとその間のディレクトリ名を除去する。

patchfile中のファイル名が 

proj-0.0.1/src/foo/bar/main.c

であったとすると、以下のように調整される。

  • "-p" 指定無し : カレントディレクトリ中のファイル、すなわち "`pwd`/main.c" が適用対象となる。
  • "-p0" or "-p" 指定時 : パス名は変更されない。"`pwd`/proj-0.0.1/src/foo/bar/main.c"が適用対象となる。
  • "-p1" 指定時 : 最初の"/"とその間のディレクトリ名が除去されるので、"proj-0.0.1/"が除去される。従って "`pwd`/src/foo/bar/main.c" が適用対象となる。
  • "-p2" 指定時 : 2番目の"/"とその間のディレクトリ名が除去されるので、"proj-0.0.1/src/"が除去される。従って "`pwd`/foo/bar/main.c" が適用対象となる。

個人的な経験として、Linuxに触りだした当時、雑誌記事を見つつソースコードを弄っていた時"-p"オプションの意味を知らずにpatchを無理矢理あててしまい、ソースコードがぐちゃぐちゃになってしまった事がある。
patchファイルを作成した人の環境と、自分の環境は必ず異なるので、"--dry-run/-C/--check"を活用して丁寧に確認してからpatchを適用するよう心がけたい。

"-R"によるロールバック

"-R"は本来の意味としては「patchfileの中の新旧が逆でした～」というpatchを当てたい時に使う。
しかし見方を変えれば、旧→新で作られた正常なpatchfileを「新→旧へのロールバック用patch」として処理する事を意味する。
従って、パッチ適用後にパッチに間違いが発見され、ロールバックしたい場合は、適用時のオプションに "-R" を加えるだけで適用前の状態にロールバックできる。 

$ patch -p1 < foobar.patch
↓ロールバックしたい・・・
$ patch -p1 -R < foobar.patch

なお、ed形式のpatchファイルについては必要な情報が不足している為、"-R"オプションは使えない。

より良いpatchファイルを作成するには

Linux jman, FreeBSDのmanページ共に「パッチを送る人への注意」「パッチ作成者への注意」という項目があり、参考になる。

  1. "patchlevel.h"というファイルを必ず更新するようにしておくと、今どのpatchlevelが当たっているのか分かりやすい。(ソースコード管理ツールが普及した今でも通用するのかな？)
  2. "diff -uNr dir_old dir_new"などで、"dir_old"や"dir_new"にスラッシュを含めない。（"-p"でのずれや混乱をなるべく抑える)
  3. 上記に関連して、"-pNum"の調整が必要な場合は、ユーザーにきちんとアナウンスする。
  4. さらに関連して、"-pNum"の調整をユーザーにお願いする場合は、diffする時のディレクトリ階層を合わせておく事。"diff foo/bar/baz/main.c baz/main.c"のようにしてしまうと"-pNum"が上手く動かなくなってしまう為。
  5. 日付については世界協定時を用いてdiffするとよい。"LC_ALL=C TZ=UTC0 diff..."とするとよい。
  6. 新規ファイルの作成や、ファイル削除については "diff -N"オプションを使ってpatchファイルを作成すると良い。
  7. リバースパッチを送らないよう注意しよう！
  8. 適当な大きさに分割する事。

プレーンテキスト形式でダウンロード
現在のバージョン : 1
更新者: msakamoto-sf
更新日: 2009-11-20 17:18:02
md5:5d28a472f55287d3cb4db18034b37867
sha1:7fe56699b2529baca74f64c8985d1224c2d86763

技術/UNIX/cpio  ↑

所有者: msakamoto-sf    作成日: 2009-11-19 18:30:07
カテゴリ: Linux UNIX シェルスクリプト 

RPMパッケージやAppleの"pax"インストーラ, Linux kernel 2.6でのinitramfsに使われていたりと、何気なく現役で使われている。
というわけで、例によって自分用メモ。

基本的な使い方

GNU cpio HTML ドキュメントにもTutorialが用意されており、基本は「Copy-out：アーカイブ作成」「Copy-in：アーカイブ展開」「Copy-pass：ディレクトリ単位でコピー」の３つのモードを使い分ける。

Copy-out : アーカイブ作成

cpio {-o|--create} その他オプション < 対象ファイル一覧 > アーカイブファイル

標準入力でファイル名の一覧を与えると、標準出力にアーカイブデータを出力する。findコマンドを組み合わせると使いやすくなる。 

$ find . -print | cpio -ov > foo.cpio

パイプでつなげれば、gzip圧縮もできる。拡張子としては".cpio.gz"や".cpgz"が使われるようだ。 

$ find . -print | cpio -o | gzip > foo.cpio.gz

Copy-in : アーカイブ展開

cpio {-i|--extract} その他オプション < アーカイブファイル

標準入力でアーカイブデータを与えると、アーカイブの展開を行う。 

$ cpio -iv < foo.cpio

"-t"オプションを指定すると、実際の展開は行わず入力ファイル名の一覧を表示するだけとなる。 

$ cpio -t < foo.cpio

Copy-pass : ディレクトリ単位でコピー

cpio {-p|--pass-through} その他オプション コピー先ディレクトリ名 < 対象ファイル一覧

例： 

$ cd <src_dir>
$ find . -print | cpio -pvd <dest_dir>

"-d"オプションをつけておくと、"<dest_dir>"が存在しない場合は自動的に作成してくれる。

その他

改行を含むファイル名

ファイル名に改行を含むファイルをアーカイブしたい場合は、"-0"または"--null"で、ファイル名の一覧がNULL区切りであることを指示しておく。
同時に、findコマンドでファイル名をNULL区切りにするよう"-print0"を使う。 

$ find . -print0 | cpio -ov0 > foo.cpio
$ find . -print0 | cpio --null -ov > foo.cpio

findコマンドと組み合わせる時の、findの"-depth"オプション

GNU cpio HTMLドキュメントのTutorialを読んでいたら、findコマンドに"-depth"オプションをつけた例がある。 

find . -print -depth | cpio -ov > tree.cpio

これについて実際に実験してみて、「何故 "-depth" 付を推奨しているのか」分かったのでメモ。ちなみにCentOS 5.2 の GNU find 4.2.27 を使うと、"-print -depth"の順にするとwarningが出てしまったので、以降は"-depth -print"の順にしている。

まず、"-depth"オプション(or "-d")を指定すると「ディレクトリ階層が深い方を優先して処理する」ようになる。
例： 

$ cd cpio_test/
$ find .
.
./foo
./foo/bar
./foo/bar/test3.txt
./foo/test2.txt
./test1.txt
$ find . -depth
./foo/bar/test3.txt
./foo/bar
./foo/test2.txt
./foo
./test1.txt
.

これとcpioを組み合わせ、展開した時の動作を考えてみる。

  • "-depth"無し：先にディレクトリを作成し、権限を復元し、次にディレクトリの中のエントリを展開していく。
  • "-depth"有り：まずディレクトリ中のエントリを展開し、最後にディレクトリの権限を復元する。

このため、"-depth"有りで作成されたcpioアーカイブを展開する時は 

cpio -i < foo.cpio

ではなくて、"-d"でディレクトリの自動作成を有効にした上で展開する必要がある。 

cpio -id < foo.cpio

もし"-d"を使わない場合は、予めディレクトリだけは作成しておく必要がある。

わざわざ"-depth"有りの動作を使う理由は、ディレクトリの権限が特殊な場合を想定しているからである。
一番分かりやすい例だと、そのディレクトリ権限の所有者bitから"w"が落ちている場合である。 

$ cd cpio_test/
$ find . | xargs ls -ld
drwxrwxr-x 3 msakamoto msakamoto 4096 11月 18 19:07 .
drwxrwxr-x 3 msakamoto msakamoto 4096 11月 18 19:09 ./foo
dr-x------ 2 msakamoto msakamoto 4096 11月 18 19:14 ./foo/bar
  ^ "test3.txt"を作成後に、chmod u-w して"w"権限を落としている。
-rw-rw-r-- 1 msakamoto msakamoto   10 11月 18 19:14 ./foo/bar/test3.txt
-rw-rw-r-- 1 msakamoto msakamoto    6 11月 18 19:08 ./foo/test2.txt
-rw-rw-r-- 1 msakamoto msakamoto    6 11月 18 19:08 ./test1.txt

この場合に、"-depth"無しでアーカイブしたcpioを展開すると、"foo/bar/test3.txt"が展開できなくなる。

  1. "./foo/bar" ディレクトリを作成＋権限を復元 → ownerの"w"フラグが落ちる。
  2. "./foo/bar/test3.txt" ファイルを作成しようとするが、ディレクトリの"w"フラグが落ちているので書き込めない。

実際にやってみる： 

$ cd cpio_test/
$ find . -print | cpio -o > ../test1.cpio
$ cd ..; mkdir test1; cd test1
$ cpio -iv < ../test1.cpio
.
foo
foo/bar
cpio: foo/bar/test3.txt: 許可がありません
foo/bar/test3.txt
foo/test2.txt
test1.txt
1 block

こういう場合に "-depth"有りでアーカイブしておけば、中のファイルツリーを展開した後で権限を復元するようになるので、問題は発生しなくなる。
実際にやってみる： 

$ cd cpio_test/
$ find . -depth -print | cpio -o > ../test2.cpio
$ cd ..; mkdir test2; cd test2
$ cpio -ivd < ../test2.cpio  # ← "-d"オプションを忘れずに！
foo/bar/test3.txt
foo/bar
foo/test2.txt
foo
test1.txt
.
1 block

プレーンテキスト形式でダウンロード
現在のバージョン : 1
更新者: msakamoto-sf
更新日: 2009-11-20 17:17:49
md5:2863537e337c35da88c7384e47b0c205
sha1:3e1dc8abe164ca9f0f95d6a5a3434807891e3207

技術/UNIX/sharutilsのuuencode,uudecodeによるBASE64エンコード,デコード  ↑

所有者: msakamoto-sf    作成日: 2004-01-07 18:03:28
カテゴリ: Linux UNIX 

メールの添付ファイルの形式として、UNIX世界では昔から Unix to Unix encode というエンコードツールが使われて来ました。現在も多くのディストリビューションで "sharutils" というパッケージ名で提供されています。

sharutils
The sharutils package contains the GNU shar utilities, a set of tools
for encoding and decoding packages of files (in binary or text format)
in a special plain text format called shell archives (shar). This
format can be sent through e-mail (which can be problematic for regular
binary files). The shar utility supports a wide range of capabilities
(compressing, uuencoding, splitting long files for multi-part
mailings, providing checksums), which make it very flexible at
creating shar files. After the files have been sent, the unshar tool
scans mail messages looking for shar files. Unshar automatically
strips off mail headers and introductory text and then unpacks the
shar files.

Install sharutils if you send binary files through e-mail.
http://www.gnu.org/software/sharutils/

このパッケージに含まれる uuencode/uudecode というツールと使うとBASE64でバイナリファイルをエンコード・デコードできます。(ヘッダとフッタにはツール独自の情報が付加される点に注意) 

エンコード：
$ cat hoge.bin | uuencode -m hoge.bin > encoded.txt
デコード：
$ cat encoded.txt | uudecode

注意点としては、まず両ツールとも標準入力からファイルを読み込むという点です。
次に、uuencodeではエンコード結果が標準出力へ流れる、という事。
また、uudecodeでは、出力ファイル名がuuencodeのエンコードしたファイルのヘッダに書いてあるため、出力ファイル名をコマンドラインで指示する必要が無いと言うこと。

試しに適当なファイルで上のサンプルみたくエンコード・デコードしてみて下さい。

もう一つ、実際にメール添付ファイルなどをPerlで処理させる際の注意点として。
uuencode/decodeでは、エンコードされたファイルの最初と最後に独自のヘッダが混じる、という点です。 

$ less encoded.txt
begin-base64 644 hoge.bin
L8hsiOdsHACLM...
....GkdshK9ds7D9KJfds==
===

このように、uuencodeは冒頭にエンコード方法と元のファイルのパーミッション、ファイル名を記述し、ファイル末尾に = を三つつけます。
これはuudecode側でチェックしているため、もしメール添付のエンコード文字列をuudecodeで復元しようと思ったら、手動でこの二つのヘッダとフッタを付け足した後、uudecodeに流し込む必要があります。
uuencodeを利用する場合はその逆で、MIMEヘッダを用意した後、エンコードされた文字列から冒頭と末尾のヘッダを除き、MIMEヘッダをつけ直す必要があります。


プレーンテキスト形式でダウンロード
現在のバージョン : 1
更新者: msakamoto-sf
更新日: 2009-11-20 11:06:26
md5:d00e015b7f2659db221ec278a8b117e7
sha1:21f4f02795103520b4ad5bae40e8e88ce027b256

技術/UNIX/「UNIX用のGeekな小技10個」メモ  ↑

所有者: msakamoto-sf    作成日: 2007-01-14 12:38:45
カテゴリ: Linux UNIX 

IBMで"10のUNIX小技"という記事があるそうです。
http://www-128.ibm.com/developerworks/aix/library/au-badunixhabits.html

で、その日本語訳。
http://www.geekpage.jp/blog/?id=2007/1/11

日本語訳の捕捉。
http://blog.livedoor.jp/dankogai/archives/50739181.html

mkdir -p とか、tarの解凍先指定とか、subshell機能とか、いろいろ便利なTips。


プレーンテキスト形式でダウンロード
現在のバージョン : 1
更新者: msakamoto-sf
更新日: 2009-11-20 11:05:53
md5:6095957f84b2b94fcc32b7aaacf384df
sha1:5c25d25438e6a84e8f0d4af452f759ab88367e6b

C言語系/memos/gettext  ↑

所有者: msakamoto-sf    作成日: 2009-11-18 16:05:11
カテゴリ: C言語 Linux 

GNU gettext の自分用メモ

(全て表示する)
プレーンテキスト形式でダウンロード
現在のバージョン : 1
更新者: msakamoto-sf
更新日: 2009-11-18 20:22:15
md5:74ea506a746e9d32c6008bc4f52940f4
sha1:851a459dc995c628642d6b4c2b1673acd9043ac6